対称分割ソートを使用する

対称分割ソート (symmetry partition sort, SPSort) は、比例拡張ソート（PESort）の分割を土台にしつつ、整列済み標本を配列の両端へ置いてから未整列部分を分割することで、クイックソートの最悪 O(n²) を避けつつ分割処理を速くする比較ソートである。

2007 年に Jing-Chao Chen により提案された。

PESort は整列済み接頭辞 S を左端に伸ばし、その中央値をピボットに未整列部分 U を分割する。

SPSort も同じ比例拡張の枠組みを使うが、分割に入る直前に S を中央値で左右に分け、左半分 L を左端、右半分 R を右端に置き、中央に U を残す L | U | R の形に整える。 L と R はそれぞれピボット未満・以上の要素群として働き、分割ループの 番兵（Sentinel） になるため、境界チェックを減らしつつ走査を速くできる。

  1. 接頭辞の初期化: 先頭 1 要素（または少数要素）を整列済み接頭辞 S とみなす。
  2. 比例拡張: |U| > p·|S| のあいだ、S と U の先頭 p·|S| 要素をまとめて整列し、結果を新しい S とする（PESort と同様）。
  3. 対称配置: S の中央値位置で左右に分け、右半分 R を配列右端へ移動して L | U | R にする。
  4. 中央値ピボット: 中央値をピボットとして U を分割する（実装では Lomuto 型や 3 路分割などが用いられる）。
  5. 再帰: 左側（L とピボット未満の部分）・右側（ピボット以上と R）に同じ手順を適用する。十分短い区間は挿入ソートで仕上げる。
procedure symmetry_partition_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)
    symmetry_partition_sort(A, lo, chunk_end, p)
    s_end = chunk_end
  median = lo + floor((s_end - lo) / 2)
  r_len = s_end - median
  move A[median + 1 .. s_end] to A[hi - r_len + 1 .. hi]   // L | U | R
  pivot = partition(A, lo, hi, median)
  symmetry_partition_sort(A, lo, pivot - 1, p)
  symmetry_partition_sort(A, pivot + 1, hi, p)

パラメータ p は PESort と同じく「未整列部分 ÷ 整列済み接頭辞」の上限である。p ≈ 16 付近で平均性能がよく、小さくすると最悪ケースが改善しやすい。

Jing-Chao Chen の実装では 適応的な連続区間の検出 や 等値キー領域を持つ分割 も組み合わされ、部分整列済み入力への適応性が高い。

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

以下のデモでは p = 2（小配列でも拡張・対称配置が見えるよう意図的に小さくしている）、小区間閾値 4、分割は Lomuto 型である。

青枠は左端の整列済み標本 L、水色は右端の R、紫は中央値ピボット、オレンジは比較、緑は交換を表す。

比例拡張ソートの記事と並べて読むと、「整列済み標本を左端だけに置くか、両端に置いて番兵にするか」の違いが対比しやすい。