1. O(n²) の壁 — 素朴なソートはなぜ遅い
バブルソートは「隣どうしを比べて、逆なら交換」をくり返すだけ。分かりやすい反面、すべてのペアを見にいくので比較回数は約 n²/2。下で永遠に回るバブルソートの比較カウンタを眺めてください。要素がたった14個でも、あっという間に数十回に膨らみます。
バブルソートの手数 — 比較回数が n²/2 に積み上がる
黄色＝いま比較している2本、緑＝確定した末尾。1周するたび最大値が右端に「浮かび上がって」確定します。ソートが終わると比較回数が表示され、自動で並べ直して再スタート。この回数がだいたい n(n−1)/2 になります。
バブル・選択・挿入ソートの比較回数 ≈ n(n−1)/2 = O(n²)
n=100 なら約 4,950 回、n=1,000 なら約 500,000 回。10倍で100倍という「二乗の壁」
POINT — 速くする鍵は「分割統治」
素朴なソートが遅いのは、毎回全体をなめているから。そこで「配列を半分に割り、小さくしてから解いて、あとで賢く合流させる」。この分割統治（divide and conquer）が、比較回数を n² から n log n へ劇的に減らす。
2. マージソート — 割って、整列して、併合する
マージソートは3ステップ。①分割：配列を中央で半分に、さらに半分に、1個になるまで割る。②統治：1個の配列は自明に整列済み。③併合（マージ）：整列済みの2本を、先頭を見比べて小さい方から取り出し、1本の整列済みに合流させる。この併合が賢さの正体です。
下のデモは1手ずつ進みます。▶で自動再生、◀▶で1手ずつ。青くハイライトされた区間が「いま処理中」、黄色の▼が併合で比べている2本の先頭、緑が併合完了です。
マージソート — 分割の木を降りて、併合しながら登る
水色の点線が「左半分｜右半分」の境目。併合では両半分の先頭（▼）だけを比べれば済むのがポイント — すでに各半分が整列済みだから。全体で比較回数は必ず n log n 前後に収まります（入力に関係なく安定して速い）。
T(n) = 2 T(n/2) + O(n) ⟹ T(n) = O(n log n)
「半分を2つ解く 2T(n/2)」＋「1回の併合 O(n)」。深さ log n × 各層 n の仕事＝n log n
POINT — マージソートの長所は「安定」と「保証」
マージソートは入力がどんな順でも必ず O(n log n)（最悪でも崩れない）。さらに同じ値の順序を保つ安定ソートでもある。弱点は併合用に作業メモリ O(n) を要すること。
3. クイックソート — ピボットで振り分ける
クイックソートも分割統治ですが、割り方が逆転の発想。まず基準の値＝ピボットを1つ選び、「ピボット未満は左、以上は右」に振り分け（パーティション）ます。するとピボットは最終的な位置に確定。あとは左右をそれぞれ同じ手順で片づけるだけ。マージと違い、併合という後処理が要りません。
下のデモではピンク＝ピボット、黄色＝いま比較中、点線の「壁」＝ピボット未満ゾーンの右端です。壁より左に小さいものが溜まっていく様子を追ってください。
クイックソート — ピボットを軸に「小さい／大きい」へ振り分ける
スキャン中の要素がピボット未満なら、壁の内側へ交換して壁を1つ右へ動かします。走査が終わったらピボットを壁の位置へ入れて確定（緑）。左右の小区間に同じことをくり返す＝再帰です。平均は O(n log n)。
注意 — クイックソートの最悪は O(n²)
すでに整列済みの配列に「右端をピボット」を続けると、毎回1個ずつしか確定せず分割が偏って O(n²) に落ちる。実装ではピボットをランダムに選ぶ／中央値を推定することでこの罠を避ける。平均は速いが「保証」はマージソートに劣る、という顔の使い分けがある。
4. なぜ O(n log n) が O(n²) に圧勝するのか
分割統治が速い理由は、たった一言。「半分にできる回数は log₂n 回しかない」から。n=1,000,000 でも半分にし続ければ約20回で1個になります。各段で全体をなめる仕事が n、その段が log n 段なので合計 n log n。下で比較回数を直接ぶつけてみましょう。
比較回数の対決 — n を大きくするほど差が桁違いに開く
橙＝バブル（n²/2）、紫＝マージ／クイック（n log₂n）。n が小さいうちは大差ないのに、n を右へ動かすと橙が一気に上へ逃げ、紫はほとんど寝たまま。右上の表に正確な比較回数と「何倍速いか」が出ます。
n log₂n ≪ n²/2 （n が大きいほど圧倒的）
n=1,000: バブル≈500,000回 / マージ≈10,000回 → 約50倍。n=100万なら約25,000倍の差
5. まとめ — 2つの高速ソートの使い分け
- 分割統治で、比較回数を O(n²) から O(n log n) へ。半分にできる回数が log n 回しかないのが本質。
- マージソート：最悪でも O(n log n) を保証、安定ソート。ただし作業メモリ O(n)。
- クイックソート：その場で（追加メモリ小）速く、キャッシュにも優しい。ただしピボット選びを誤ると最悪 O(n²)。
一歩先へ — 比較の限界と、それを破る方法
実は「2つを比べる」だけで並べるソートは、どんな工夫をしてもΩ(n log n) より速くできないことが数学的に証明されている（n個の並び順は n! 通りあり、それを二分木で区別するには log₂(n!)≈n log n 回の比較が要る）。だから実務の標準は、マージとクイックと挿入を組み合わせたハイブリッド（Python の Timsort、C++ の introsort）。さらに、比較をやめて桁やバケツで振り分ける基数ソート・計数ソートは、条件が合えばO(n) すら達成する — 「比較しない」という発想の飛躍でこの壁を越える。