比例拡張ソートを使用する

比例拡張ソート (proportion extend sort, PESort) は、クイックソートの分割を土台にしつつ、整列済み接頭辞の中央値をピボットに使い、未整列部分の長さを比例定数 p で抑えることで、 クイックソートの最悪 O(n²) を避けようとする比較ソートである。2001 年に Jing-Chao Chen により提案された。

クイックソートは分割が 1 回の走査で済み、現代 CPU のメモリ階層と相性がよい。一方、ピボット選びが偏ると片側だけ巨大な部分問題が残り、最悪時間計算量が O(n²) になりうる。

PESort は 整列済み接頭辞 S と 未整列部分 U に区間を分けて考え、|U| が p·|S| を超える間は S と U の先頭 p·|S| 要素をまとめて整列して S を伸ばす。十分短い U だけが残ったら S の中央値 をピボットに分割し、左右へ再帰する。サンプルソートに近い「小さな整列済み標本からピボットを得る」発想である。

  1. 接頭辞の初期化: 先頭 1 要素（または少数要素）を整列済み接頭辞 S とみなす。
  2. 比例拡張: |U| > p·|S| のあいだ、S と U の先頭 p·|S| 要素をまとめて整列し、結果を新しい S とする。
  3. 中央値ピボット: S の中央値をピボットとして部分配列を分割する（実装では Lomuto 型などクイックソートと同様の分割が用いられる）。
  4. 再帰: ピボットより小さい側・大きい側に同じ手順を適用する。十分短い区間は挿入ソートで仕上げる。
procedure proportion_extend_sort(A, lo, hi, p)
  if hi - lo <= INSERTION_THRESHOLD then
    insertion_sort(A, lo, hi)
    return
  s_end = lo
  while s_end < hi and (hi - s_end) > p * (s_end - lo + 1)
    chunk_end = min(s_end + p * (s_end - lo + 1), hi)
    proportion_extend_sort(A, lo, chunk_end, p)
    s_end = chunk_end
  median = lo + floor((s_end - lo) / 2)
  pivot = partition(A, lo, hi, median)
  proportion_extend_sort(A, lo, pivot - 1, p)
  proportion_extend_sort(A, pivot + 1, hi, p)

パラメータ p は「未整列部分 ÷ 整列済み接頭辞」の上限である（文献によって定義が異なるので実装時は論文・ソースの取り方に注意する）。p ≈ 16 付近で平均性能がよく、p を小さくすると最悪ケースが改善しやすい。p が無限大に近いとクイックソート、未整列部分が 1 要素に近いと二分探索挿入ソートに近い振る舞いになる。

最悪・平均とも O(n log n) 比較、補助領域は再帰スタックで O(log n) とされる。安定ソートではない。

以下のデモでは p = 2（小配列でも拡張フェーズが見えるよう意図的に小さくしている）、小区間閾値 4、分割は Lomuto 型である。青枠は整列済み接頭辞、紫は中央値ピボット、オレンジは比較、緑は交換を表す。

クイックソートやイントロソートと並べて読むと、「分割の速さ」と「最悪ケースの抑え方」のトレードオフが対比しやすい。