ソートアルゴリズムの内部と下界（比較ソートの限界）

三大比較ソートの内部挙動

実用的な高速ソートはほぼ分割統治か、ヒープ構造の利用に集約されます。まず内部を正確に押さえます。各操作の計算量記法に不安があれば計算量と Big-O 記法を先に確認してください。

クイックソートは、ピボットを1つ選び、それより小さい要素と大きい要素にその場で分割（パーティション）し、各部分に再帰します。

partition(arr, lo, hi):
  pivot = arr[hi]
  i = lo - 1
  for j in lo..hi-1:
    if arr[j] <= pivot:
      i += 1; swap(arr[i], arr[j])
  swap(arr[i+1], arr[hi]); return i+1

分割が毎回ほぼ半々なら深さ log n で平均 O(n log n)。追加メモリは再帰スタックの O(log n) だけで、定数倍が小さく実測が速いのが最大の利点です。ただしピボットが毎回偏ると分割が 1 と n-1 に割れ、深さ n で最悪 O(n²)。整列済みや同値だらけの入力で起きやすく、ランダム化ピボットや三分割（3-way）で回避します。

マージソートは配列を半分に割り、各半分をソートしてから併合します。併合は2つの整列列を先頭から比較して取り出す処理で、必ず O(n)。分割の深さは常に log n なので最悪でも安定して O(n log n)。一方で併合に作業用配列が要り、O(n) の追加メモリを使います。等しい要素の相対順序を保つ安定ソートにできる点も重要です。

ヒープソートは配列を二分ヒープに組み（O(n)）、根（最大値）を末尾と交換して縮めながら取り出します。最悪 O(n log n) を追加メモリ O(1) で達成する唯一格ですが、メモリアクセスが飛び飛びでキャッシュ効率が悪く、実測はクイックに劣りがちです。ヒープ自体の構造はデータ構造の延長として押さえると理解が早まります。

なぜ n log n より速くできないのか

ここが本題です。比較だけで並べる（比較ソート）かぎり、最悪計算量は Ω(n log n) を下回れません。証明は決定木モデルで行います。

アルゴリズムが行う「a と b のどちらが大きいか」という各比較は、Yes/No に分岐する木の節点に対応します。実行は根から葉までの1本の経路で、葉は最終的に出力する並び順を表します。

ここで決定的なのは、n 個の要素には n! 通りの並び（順列）があり、そのどれか1つに必ず到達できなければ正しく並べられないこと。つまり葉は最低でも n! 個必要です。

比較1回 = 1つの分岐（高さ +1）
高さ h の二分木の葉は最大 2^h 個

正しさの要請:   2^h >= n!
両辺の対数:     h >= log2(n!)
スターリング近似: log2(n!) ≈ n log2 n
∴ 最悪の比較回数 h = Ω(n log n)

最悪の入力では根から最も深い葉までたどるので、比較回数は木の高さ以上。高さは log2(n!)、すなわち Ω(n log n) 以上になります。マージ・ヒープがこの下界に達しており、これ以上の改善は比較ソートの枠内では原理的に不可能――これが「比較ソートの限界」です。

Timsort: 下界を“破らずに”速くする設計

Python の sorted や Java の Arrays.sort（オブジェクト配列）が採用するTimsortは、この下界を理解したうえでの実用設計の好例です。下界そのものは破れません。代わりに現実の入力が持つ偏りを利用して定数と平均を削ります。

設計判断の核心は次の3点です。

• run の検出: 実データは部分的に整列済みのことが多い。連続する昇順（または降順）の並び＝run をまず走査で見つけ、降順 run は反転して整列済みブロックとして扱う。既に並んでいる入力には O(n) で済む。
• 短い run の補強: run が一定長（minrun）に満たなければ挿入ソートで伸ばす。挿入ソートは小規模・ほぼ整列済みで定数倍が小さく速い、という性質を活かす。
• 賢い併合: run をスタックに積み、サイズのバランス規則（galloping を含む）に従ってマージソート同様に併合する。これにより最悪でも O(n log n) と安定性を保証する。

実装を選ぶときの判断基準

下界が教えてくれるのは「漸近的な速さでは差がつかない」こと。だから実務の選択は最悪保証・メモリ・安定性・実データの傾向で決まります。

• 汎用・実測重視で最悪も許容できる → クイックソート（ライブラリは Introsort 等で最悪を O(n log n) に抑える実装が主流）。
• 最悪を保証したい／安定性が要る → マージソート系。レコードを複数キーで段階的に並べる用途では安定性が効く。
• 追加メモリを使えない → ヒープソート。
• 入力が部分的に整列済みになりがち → Timsort 系。ログのほぼ時系列、追記中心のデータなどで特に有利。

「どれが一番速いか」ではなく「この入力と制約で、最悪・メモリ・安定性のどれを守りたいか」を起点に選ぶ。下界の理解は、その判断を曖昧さなく行うための土台になります。