サンプルソートで配列を並び替える

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

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

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

サンプリング: 配列から s 個の要素を（等間隔に）選び、サンプル集合を得る。文献では s ≈ √n や s = p−1 などが用いられる。
サンプルの整列: サンプルだけを整列し、昇順のスプリッター列 t₀ ≤ t₁ ≤ … を得る。
仕分け: 各要素 x を、t₀, t₁, … と比較して属するバケット番号を決める（例: x ≤ t₀ ならバケット 0、t₀ < x ≤ t₁ ならバケット 1、…）。
バケット整列: 各バケットを独立に整列する（再帰的にサンプルソート、または十分小さければ挿入ソートなど）。
連結: バケット 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) になりやすく、安定ソートではない実装が多い（仕分けとバケット内ソートで等値の順序が入れ替わりうる）。

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

以下のデモでは 15 要素から 4 個のサンプルを取り、スプリッター 4 個で 5 バケットに仕分けたあと、各バケットを挿入ソートで仕上げる。

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

計算時間量および空間計算量を計測する

Size	Average time	Maximum time	Average memory	Maximum memory
256	0.000007	0.000612	1670	1680
512	0.000017	0.000560	1680	1692
1024	0.000033	0.000287	1698	1712
2048	0.000066	0.000591	1732	1748
4096	0.000138	0.000508	1796	1812
8192	0.000268	0.000894	1914	1936
16384	0.000516	0.000998	2147	2176
32768	0.001039	0.001872	2502	2624
65536	0.002113	0.005222	3327	3504
131072	0.004383	0.017335	5101	5248
262144	0.008959	0.138425	8601	8832

計測に使用したコードを表示する

set -euo pipefail

WORKDIR="$(mktemp -d)"
trap 'rm -rf "$WORKDIR"' EXIT

cat > "$WORKDIR/Dockerfile" <<'EOF'
FROM rust:1.95.0

WORKDIR /app

RUN mkdir -p src

RUN cat > Cargo.toml <<'CARGO'
[package]
name = "rust-benchmark"
version = "0.1.0"
edition = "2021"

[profile.release]
lto = true
codegen-units = 1
panic = "abort"
CARGO

RUN cat > src/main.rs <<'RUST'
use std::{
    env,
    process::Command,
    time::{Duration, Instant},
};
const MIN_POWER: u32 = 8;
const MAX_POWER: u32 = 18;
const RUNS: usize = 8192;
fn insertion_sort(a: &mut [usize]) {
    for i in 1..a.len() {
        let mut j = i;
        while j > 0 && a[j - 1] > a[j] {
            a.swap(j - 1, j);
            j -= 1;
        }
    }
}
fn partition_at(a: &mut [usize], lo: usize, hi: usize, pivot_idx: usize) -> usize {
    a.swap(pivot_idx, hi);
    let pivot = a[hi];
    let mut i = lo;
    for j in lo..hi {
        if a[j] < pivot {
            a.swap(i, j);
            i += 1;
        }
    }
    a.swap(i, hi);
    i
}
fn partition(a: &mut [usize], lo: usize, hi: usize) -> usize {
    partition_at(a, lo, hi, lo + (hi - lo) / 2)
}
fn quick_sort_range(a: &mut [usize], lo: usize, hi: usize) {
    if hi <= lo {
        return;
    }
    if hi - lo < 16 {
        insertion_sort(&mut a[lo..=hi]);
        return;
    }
    let p = partition(a, lo, hi);
    if p > 0 {
        quick_sort_range(a, lo, p - 1);
    }
    quick_sort_range(a, p + 1, hi);
}

fn quick_sort(a: &mut [usize]) {
    if let Some(hi) = a.len().checked_sub(1) {
        quick_sort_range(a, 0, hi);
    }
}
fn sample_sort(a: &mut [usize]) {
    if a.len() <= 32 {
        insertion_sort(a);
        return;
    }
    let sample_count = (a.len() as f64).sqrt() as usize;
    let step = (a.len() / sample_count.max(1)).max(1);
    let mut splitters: Vec<usize> = (step - 1..a.len())
        .step_by(step)
        .take(sample_count)
        .map(|i| a[i])
        .collect();
    quick_sort(&mut splitters);
    let mut buckets = vec![Vec::new(); splitters.len() + 1];
    for &value in a.iter() {
        let bucket = splitters.partition_point(|&splitter| value > splitter);
        buckets[bucket].push(value);
    }
    let mut pos = 0;
    for bucket in buckets.iter_mut() {
        sample_sort(bucket);
        for &value in bucket.iter() {
            a[pos] = value;
            pos += 1;
        }
    }
}

fn benchmark_sort(array: &mut [usize]) {

    sample_sort(array);

}

fn shuffled(size: usize, seed: u64) -> Vec<usize> {
    let mut v: Vec<usize> = (1..=size).collect();

    let mut state = seed;

    for i in (1..size).rev() {
        state ^= state << 13;
        state ^= state >> 7;
        state ^= state << 17;

        let j = (state as usize) % (i + 1);

        v.swap(i, j);
    }

    v
}

fn memory_usage_kb() -> usize {
    let contents = std::fs::read_to_string("/proc/self/status")
        .unwrap_or_default();

    for line in contents.lines() {
        if let Some(rest) = line.strip_prefix("VmHWM:") {
            let kb = rest
                .split_whitespace()
                .next()
                .unwrap_or("0")
                .parse::<usize>()
                .unwrap_or(0);

            return kb;
        }
    }

    0
}

fn micros(d: Duration) -> u128 {
    d.as_micros()
}

fn run_once(size: usize, seed: usize) -> (u128, usize) {
    let expected: Vec<usize> = (1..=size).collect();
    let mut array = shuffled(size, seed as u64);

    let start = Instant::now();

    benchmark_sort(&mut array);

    let elapsed = start.elapsed();

    if array != expected {
        panic!(
            "sort failed with seed {} for size {}",
            seed,
            size
        );
    }

    (micros(elapsed), memory_usage_kb())
}

fn run_child(args: &[String]) {
    let size = args[2].parse::<usize>().expect("invalid size");
    let seed = args[3].parse::<usize>().expect("invalid seed");
    let (elapsed_us, mem) = run_once(size, seed);
    println!("{} {}", elapsed_us, mem);
}

fn main() {
    let args: Vec<String> = env::args().collect();
    if args.get(1).is_some_and(|arg| arg == "--run-once") {
        run_child(&args);
        return;
    }

    println!(
        "| {:>10} | {:>15} | {:>15} | {:>15} | {:>15} |",
        "Size",
        "Average time",
        "Maximum time",
        "Average memory",
        "Maximum memory"
    );

    println!(
        "|{:-<11}:|{:-<16}:|{:-<16}:|{:-<16}:|{:-<16}:|",
        "",
        "",
        "",
        "",
        ""
    );

    for power in MIN_POWER..=MAX_POWER {
        let size = 1usize << power;

        let mut total_time: u128 = 0;
        let mut max_time: u128 = 0;

        let mut total_mem: usize = 0;
        let mut max_mem: usize = 0;

        for seed in 1..=RUNS {
            let output = Command::new(env::current_exe().expect("failed to find current executable"))
                .arg("--run-once")
                .arg(size.to_string())
                .arg(seed.to_string())
                .output()
                .expect("failed to run benchmark child process");

            if !output.status.success() {
                panic!(
                    "benchmark child process failed: {}",
                    String::from_utf8_lossy(&output.stderr)
                );
            }

            let stdout = String::from_utf8(output.stdout)
                .expect("child process returned non-UTF-8 output");
            let mut fields = stdout.split_whitespace();
            let elapsed_us = fields
                .next()
                .expect("missing elapsed time")
                .parse::<u128>()
                .expect("invalid elapsed time");
            let mem = fields
                .next()
                .expect("missing memory usage")
                .parse::<usize>()
                .expect("invalid memory usage");

            total_time += elapsed_us;

            if elapsed_us > max_time {
                max_time = elapsed_us;
            }

            total_mem += mem;

            if mem > max_mem {
                max_mem = mem;
            }
        }

        let avg_time = total_time / RUNS as u128;
        let avg_mem = total_mem / RUNS;

        println!(
            "| {:>10} | {:>15} | {:>15} | {:>15} | {:>15} |",
            size,
            format!("{}.{:06}", avg_time / 1_000_000, avg_time % 1_000_000),
            format!("{}.{:06}", max_time / 1_000_000, max_time % 1_000_000),
            avg_mem,
            max_mem
        );
    }
}
RUST

RUN cargo build --release

CMD ["./target/release/rust-benchmark"]
EOF

docker build -t rust-benchmark "$WORKDIR"
docker run --rm --init rust-benchmark