クイックソート — Project Hematite

マージソートはすべてのケースで $\Theta(n \log n)$ を保証するが $O(n)$ の余分なメモリが必要だ。クイックソートは $O(1)$ の余分な空間を使い、その平均ケースも $O(n \log n)$ で — マージソートより小さい定数倍だ。ランダムな入力に対してクイックソートは通常最も速い比較ソートであり、C（qsort）、C++（std::sort）などの標準ライブラリソーターを支えている。

中心的なアイデア

クイックソートは分割統治アルゴリズムだ：

ピボットを選ぶ — 配列から 1 つの要素を選ぶ。
分割 — ピボットより小さいすべての要素が左に、大きいすべての要素が右になるよう配列をインプレースで並べ替える。ピボットは最終的なソート済み位置に収まる。
再帰 — 左部分配列と右部分配列を独立してソートする。

魔法はステップ 2 にある：分割は $O(n)$ 時間で動作し余分なメモリを必要としない。

Lomuto 分割スキーム

いくつかの分割アルゴリズムがある。Lomuto 分割（Lomuto partition）はシンプルで理解・実装しやすい。最後の要素をピボットとして使い、左から右にスキャンしながら 2 つの領域を維持する：

arr[lo..i] — ピボット以下の要素（「小さい」領域、右に伸びる）
arr[i..j] — ピボットより大きい要素（「大きい」領域）
arr[j] — 次に分類する要素

スキャン完了後、（まだ arr[arr.len - 1] にある）ピボットが位置 i にスワップされ、そこが永続的な位置になる。

/// arr をインプレースで分割し、ピボットの最終インデックスを返す。
fn partition(arr: []i64) usize {
    const pivot = arr[arr.len - 1];
    var i: usize = 0; // 境界：arr[0..i] はピボット以下の要素を含む

    for (0..arr.len - 1) |j| {
        if (arr[j] <= pivot) {
            // arr[j] を小さい領域に移動する。
            const tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i += 1;
        }
    }

    // ピボットを境界に置く。
    const tmp = arr[i];
    arr[i] = arr[arr.len - 1];
    arr[arr.len - 1] = tmp;

    return i;
}

fn quickSort(arr: []i64) void {
    if (arr.len <= 1) return;
    const p = partition(arr);
    quickSort(arr[0..p]);
    if (p + 1 < arr.len) quickSort(arr[p + 1 ..]);
}

正しさ

partition がインデックス p を返した後：

arr[p] はピボットと等しく最終位置にある。
arr[0..p] のすべての要素は arr[p] 以下だ。
arr[p+1..] のすべての要素は arr[p] 以上だ。

quickSort は同じ議論で各側を再帰的にソートする。基底ケース（arr.len ≤ 1）は自明にソートされている。

計算量

平均ケース： $O(n \log n)$

最良ケースではピボットが常にちょうど中央に落ちるので、漸化式は $T(n) = 2T(n/2) + O(n)$ — マージソートと同じ — で $O(n \log n)$ に解ける。

ランダムなピボットでは期待される分割が完璧に均等ではないが、比較の期待数はそれでも $O(n \log n)$ だ（約 $2n \ln n$ ）。証明はすべてのペア $(i, j)$ が最大 1 回比較されるという事実を使い、要素 $i$ と $j$ が比較される確率は $\frac{2}{j - i + 1}$ なので期待される総比較数は $O(n \log n)$ に収束する。

最悪ケース： $O(n^2)$

ピボットが常に最小または最大要素のとき、一方の分割がサイズ $n - 1$ で他方がサイズ $0$ になる：

T(n) = T(n-1) + O(n) \implies T(n) = O(n^2).

これはピボットが常に最後の要素のとき、既にソート済み（または逆ソート）の入力で発生する — 現実でよくあるケースだ。

空間

クイックソートはインプレース（補助配列なし）だが、再帰呼び出しのために平均 $O(\log n)$ のスタック空間を使う。最悪ケースでは再帰の深さが $O(n)$ になり、大きな入力ではコールスタックがオーバーフローすることがある。

ピボットの選択

ピボット戦略が実際に最悪ケースに当たるかどうかを決める：

戦略	最悪ケース入力	備考
最後の要素	ソート済みまたは逆ソート入力	最も実装が単純
ランダムな要素	まれ（特定の順列）	単純な修正：ランダムな要素を最後にスワップしてから実行
3 要素中央値	特定の構成が必要	`arr[0]`、`arr[mid]`、`arr[arr.len-1]` の中央値をピボットとして選ぶ

ランダム化クイックソート — 一様ランダムにピボットを選ぶ — は入力分布に関わらず期待 $O(n \log n)$ 時間を与える。特定の入力が最悪ケースになることはできない。実行ごとに異なるランダムなピボットが選ばれるからだ。

クイックソートは安定でない

Lomuto 分割は元の相対順序を考慮せずに配列全体で要素をスワップする。等しい要素が異なる位置に来ることがある。安定性が必要ならマージソートを使う。

クイックソートとマージソートの比較

特性	クイックソート	マージソート
最悪ケース時間	$O(n^2)$	$\Theta(n \log n)$
平均ケース時間	$O(n \log n)$	$\Theta(n \log n)$
余分な空間	$O(\log n)$ （スタック）	$O(n)$
安定	いいえ	はい
キャッシュ挙動	優秀（インプレース）	低い（バッファにコピー）

クイックソートのキャッシュ性能の良さが、理論的な最悪ケースが悪いにもかかわらずランダム入力のベンチマークで勝つ傾向がある理由だ。

まとめ

クイックソートはピボットの周りで配列を分割してピボットを最終位置に置き、各側を再帰的にソートする。
Lomuto 分割は左から右にスキャンしてピボット以下の要素を増大する左領域に置き、境界にピボットをスワップする。
平均ケース時間は $O(n \log n)$ 、最悪ケースは $O(n^2)$ （素朴なピボットでソート済み入力の場合）。
ピボットをランダムに選ぶと予測可能な最悪ケースを避けられる。
空間は平均 $O(\log n)$ （コールスタック）、最悪 $O(n)$ ；補助配列は不要だ。
クイックソートは安定でない。
キャッシュ挙動の良さからマージソートより実用的に高速なことが多い。最悪ケース保証は弱いが。