クイックソートは平均計算量が O(n log n) である一方、ピボット選択が悪い場合に最悪 O(n²) に退化する。本稿では、Java で実装可能な高速化テクニックを段階的に紹介する。

1. 単純な二方向分割

ピボットを末尾に固定したまま、slow / fast という２つの走査ポインタを使って「ピボット未満」を左に集める手法。

static void basicQuick(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = a[hi];
    int slow = lo, fast = lo;
    while (fast < hi) {
        if (a[fast] < pivot) swap(a, slow++, fast);
        fast++;
    }
    swap(a, slow, hi);
    basicQuick(a, lo, slow - 1);
    basicQuick(a, slow + 1, hi);
}

このコードは整列済み配列では深さ n の再帰を生じ、実行時間が爆発する。

2. ランダムピボットによる退化防止

ピボット位置をランダムに選ぶことで、整列済み入力に対する耐性を得る。

static void randomizedQuick(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int r = ThreadLocalRandom.current().nextInt(lo, hi + 1);
    swap(a, r, hi);
    int pivot = a[hi];
    int slow = lo, fast = lo;
    while (fast < hi) {
        if (a[fast] < pivot) swap(a, slow++, fast);
        fast++;
    }
    swap(a, slow, hi);
    randomizedQuick(a, lo, slow - 1);
    randomizedQuick(a, slow + 1, hi);
}

3. 三区分割（Dutch National Flag）

重複値が多数含まれる場合、ピボットと等しい要素を再帰対象から除外すると大幅に高速化できる。
lt 未満、gt より大きい領域を境界として３領域に分割する。

static void threeWayQuick(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int r = ThreadLocalRandom.current().nextInt(lo, hi + 1);
    swap(a, r, hi);
    int pivot = a[hi];

    int lt = lo, i = lo, gt = hi;
    while (i <= gt) {
        if (a[i] < pivot)      swap(a, lt++, i++);
        else if (a[i] > pivot) swap(a, i, gt--);
        else                   i++;
    }
    threeWayQuick(a, lo, lt - 1);
    threeWayQuick(a, gt + 1, hi);
}

4. 挿入ソートとのハイブリッド化

小さい区間では関数呼び出しコストが支配的になるため、要素数が閾値（経験的に 40～50）以下の場合は挿入ソートに切り替える。

static final int INSERTION_THRESHOLD = 44;

static void insertion(int[] a, int lo, int hi) {
    for (int i = lo + 1; i <= hi; i++) {
        int key = a[i], j = i - 1;
        while (j >= lo && a[j] > key) a[j + 1] = a[j--];
        a[j + 1] = key;
    }
}

static void hybridQuick(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    if (hi - lo + 1 <= INSERTION_THRESHOLD) {
        insertion(a, lo, hi);
        return;
    }
    int r = ThreadLocalRandom.current().nextInt(lo, hi + 1);
    swap(a, r, hi);
    int pivot = a[hi];

    int lt = lo, i = lo, gt = hi;
    while (i <= gt) {
        if (a[i] < pivot)      swap(a, lt++, i++);
        else if (a[i] > pivot) swap(a, i, gt--);
        else                   i++;
    }
    hybridQuick(a, lo, lt - 1);
    hybridQuick(a, gt + 1, hi);
}

まとめ

上記の最終実装は、ランダムピボットと三区分割で退化を回避し、小さい区間では挿入ソートにフォールバックすることで、LeetCode 912「Sort an Array」で 20 ms 台の高速実行を達成した。