サンプルソートを使用する

サンプルソート (sample sort) は、入力から 少数の標本（サンプル） を取り出して整列し、その値を 分割点（スプリッター） として全体を バケット（区間） に分け、 各バケットを独立に整列してから連結する比較ソートである。並列計算向けに設計された手法として知られ、プロセッサ数 p に対して p−1 個のスプリッター を選ぶ構成が典型である。

クイックソートが 1 つのピボット で左右に分けるのに対し、サンプルソートは 複数のスプリッター で p 個（デモでは要素数に応じた複数個）のバケット に一度に仕分ける。分割の偏りを抑えやすく、各バケットを 別プロセッサで同時に 整列できる点が並列版の利点である。

  1. サンプリング: 配列から s 個の要素を（等間隔に）選び、サンプル集合を得る。文献では s ≈ √n や s = p−1 などが用いられる。
  2. サンプルの整列: サンプルだけを整列し、昇順のスプリッター列 t₀ ≤ t₁ ≤ … を得る。
  3. 仕分け: 各要素 x を、t₀, t₁, … と比較して属するバケット番号を決める（例: x ≤ t₀ ならバケット 0、t₀ < x ≤ t₁ ならバケット 1、…）。
  4. バケット整列: 各バケットを独立に整列する（再帰的にサンプルソート、または十分小さければ挿入ソートなど）。
  5. 連結: バケット 0, 1, … の順に並べれば全体が昇順になる。
procedure sample_sort(A, s)
  if length(A) <= SMALL then
    insertion_sort(A)
    return
  S = choose_s_samples(A, s)
  sort(S)
  splitters = S
  buckets = empty list of s + 1 arrays
  for each x in A
    b = bucket_index(x, splitters)
    append x to buckets[b]
  for each bucket B in buckets
    sample_sort(B, s)
  A = concatenate(buckets)

並列モデルではステップ 3〜4 を各バケットごとに同時実行でき、要素数 n・プロセッサ数 p が釣り合うとき O(n/p) 程度の並列時間 を狙える。 逐次実行に落とすと、再帰の深さとバケットサイズのバランス次第だが、比較回数は O(n log n) オーダーに収まる設計が一般的である。 追加メモリはバケット用バッファ分 O(n) になりやすい。安定ソートではない 実装が多い（仕分けとバケット内ソートで等値の順序が入れ替わりうる）。

比例拡張ソート（PESort）のように「小さな整列済み標本から分割点を得る」発想はサンプルソートと共通する。バブルソートのように隣接交換だけで進む単純ソートや、クイックソートの 単一ピボット再帰 と比べると、標本に基づく多分割 と 並列化しやすい区切り が特徴的である。

以下のデモでは 15 要素から 4 個のサンプル を取り、スプリッター 4 個で 5 バケット に仕分けたあと、各バケットを挿入ソートで仕上げる。紫枠はスプリッター（整列済みサンプル）、オレンジは比較、緑は交換を表す。

外部ソートや分散整列の文脈では、サンプルソートは I/O 効率のよい分割 としても使われる。実装ではサンプル数、再帰の打ち切り、等値要素の扱い（3-way 分割など）が性能を左右するため、クイックソート単体より パラメータとメモリ使用量 の設計が重要になる。