イントロソートを使用する

イントロソート (introspective sort) は、クイックソートを主役にしつつ、再帰が深くなりすぎたらヒープソートに切り替え、さらに 十分に短い部分配列では挿入ソート で仕上げる、現実的な ハイブリッド整列 である。

David R. Musser が 1997 年に提案し、最悪時間計算量を O(n log n) に保ちながら、平均的にはクイックソートに近い速度を狙える。

クイックソート単体は入力次第でピボット選びが偏り、再帰深度が O(n) になり 最悪 O(n²) になり得る。

イントロソートは 許容する再帰の深さに上限（多くの実装で 2·⌊log₂ n⌋ 前後）を設け、それを超えそうな区間だけヒープソートにフォールバックすることで、比較ソートとしての下界 Ω(n log n) に張り付いたまま、最悪ケースを回避する。

  1. クイックソート: 通常どおり分割と再帰を行う。
  2. 深さの監視: 再帰の残り許容深度が 0 になった区間は、クイックソートを続けず ヒープソート で処理する。
  3. 小区間の挿入: 要素数が閾値以下の部分配列は 挿入ソート で済ませる（再帰オーバーヘッドとマージコストを抑える）。
procedure introsort(A, lo, hi, depth_limit)
  if hi - lo <= INSERTION_THRESHOLD then
    insertion_sort(A, lo, hi)
    return
  if depth_limit = 0 then
    heapsort(A, lo, hi)
    return
  p = partition(A, lo, hi)
  introsort(A, lo, p - 1, depth_limit - 1)
  introsort(A, p + 1, hi, depth_limit - 1)

procedure sort(A)
  introsort(A, 0, length(A) - 1, max(2 * floor(log2(length(A))), 1))

全体として 比較による最悪時間計算量は O(n log n)（ヒープソート区間が支配的になりうる）、追加メモリは実装次第だがヒープソート部分で O(1) のインプレース志向を保ちやすい。安定ソートではない 場合が多い（ピボット型の分割・挿入ソートの交換が相対順序を変えうる）。

C++ の std::sort や、一部言語ランタイムの汎用ソートが、クイックソート系＋フォールバックという構成をとることがある。教育的には バブルソート のように単純な比較ソートと対比すると、「平均の速さ」と「最悪保証」を両立する設計意図が把握しやすい。

以下のデモでは 閾値・深さ計算を実装と揃えたうえで、オレンジは比較、緑は交換、紫は確定したピボット、青系は挿入ソート中の強調、ヒープフェーズ開始時はキャプションで明示する。昇順に近いデータではクイックソートの分割が偏りやすく、ヒープソートへの切り替え が現れやすい。

ピボット選択や閾値、切片アルゴリズムは実装ごとに異なるが、「高速な平均ケースとしてのクイックソート」と「保証された最悪効率としてのヒープソート」を組み合わせるという発想は、整列アルゴリズムを実務レベルへ押し上げる典型的な一手である。