パワーソートで配列を並び替える

パワーソートを使用する

パワーソート (Powersort) は、James Ian Munro と Sebastian Wild が 2018 年に提案した安定な比較ソートである。

ティムソートと同じく すでに整列している連続区間（ラン） を見つけ、マージソートの枠組みで併合する 適応型（adaptive） アルゴリズムだが、どのラン同士をいつマージするか の方針だけを差し替えた改良版と捉えられる。

Python 3.11 以降の list.sort() では、ラン検出や短いランの拡張などティムソート由来の仕組みを保ったまま、マージ方針がパワーソートに置き換わっている。

ランの検出: 左から昇順または厳密な降順の連続区間を見つける。降順ランは反転して昇順にそろえる。
ランの拡張: 長さが 最小ラン長 min_run 未満なら挿入ソートで伸ばす（デモでは見やすさのため 4 に固定）。
パワーの計算: 隣接する 2 ランの「中点位置」から、理想のマージ木上での ノードの深さ に相当する整数 パワー を求める。
スタックに従ったマージ: 未マージのランをスタックに積み、新しいパワーがスタック先端より小さくなるまで 左側のラン と 現在のラン を併合する。
仕上げ: 入力末尾まで進んだあと、スタックに残ったランをすべてマージして全体を整列する。

ティムソートはスタック上端 3 本 の長さ関係を見る 経験則 でマージ順を決めていた。

パワーソートは 2 ランの中点 だけからパワーを 1 つ計算し、ほぼ最適な二分マージ木 に沿う順序で併合する。ラン検出や短いランの拡張はティムソートと同じ思想だが、マージ順の決め方だけが パワー という 1 つの整数に集約される点が特徴である。

理論上、既存ラン長 (L₁, …, Lᵣ) に対する適応性は、加法項 O(n) を除き最適に近い。

procedure node_power(n, b1, e1, b2, e2)
  n1 := e1 - b1
  n2 := e2 - b2
  a := (b1 + n1/2) / n
  b := (b2 + n2/2) / n
  p := 0
  while floor(a · 2^p) = floor(b · 2^p) do
    p := p + 1
  return p

procedure powersort(A)
  S := empty stack of (run, power)
  b1 := 0; e1 := first_run_end(A, 0)
  while e1 < length(A)
    b2 := e1; e2 := first_run_end(A, b2)
    P := node_power(length(A), b1, e1, b2, e2)
    while S is not empty and S.top().power > P
      (b1, e1) := merge(S.pop().run, A[b1..e1))
    S.push((A[b1..e1), P))
    b1 := b2; e1 := e2
  while S is not empty
    (b1, e1) := merge(S.pop().run, A[b1..e1])

最悪時間計算量 は O(n log n)。安定ソート であり、等しいキーの相対順序を保つ。

補助領域はマージ用に O(n) が必要になることが多い。

ティムソートと比べ、特定のラン長パターンで起きうる 非効率なマージ（理論上最大で約 50% のオーバーヘッド）を避けやすく、スタック高さも O(log n) で抑えられる。

実装の複雑さはティムソートの 3 本ルールより読み取りやすく、理論的な保証も強い一方、パワー計算やマージ用バッファなどオーバーヘッドは残るため、教育用の最小例としてはマージソート単体のほうが追いやすい場合もある。

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

Size	Average time	Maximum time	Average memory	Maximum memory
256	0.000007	0.000120	1666	1672
512	0.000015	0.000418	1673	1680
1024	0.000033	0.000428	1685	1692
2048	0.000083	0.000455	1710	1716
4096	0.000168	0.000728	1758	1764
8192	0.000347	0.000672	1854	1860
16384	0.000741	0.000989	2050	2056
32768	0.001629	0.005818	2437	2444
65536	0.003547	0.009432	3200	3328
131072	0.007585	0.015037	5107	5112
262144	0.016980	0.120476	8691	8696

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

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;
        }
    }
}
#[derive(Clone, Copy)]
struct PowerRun {
    lo: usize,
    hi: usize,
    power: u32,
}

fn node_power(n: usize, b1: usize, e1: usize, b2: usize, e2: usize) -> u32 {
    let a = (b1 as f64 + (e1 - b1) as f64 / 2.0) / n as f64;
    let b = (b2 as f64 + (e2 - b2) as f64 / 2.0) / n as f64;
    let mut p = 0u32;
    while (a * 2f64.powi(p as i32)).floor() == (b * 2f64.powi(p as i32)).floor() {
        p += 1;
    }
    p
}

fn merge_power_runs(a: &mut [usize], left: PowerRun, right: PowerRun) -> PowerRun {
    let lo = left.lo;
    let hi = right.hi;
    let mid = left.hi + 1;
    let mut merged = Vec::with_capacity(hi - lo + 1);
    let (mut l, mut r) = (left.lo, mid);
    while l <= left.hi && r <= right.hi {
        if a[l] <= a[r] {
            merged.push(a[l]);
            l += 1;
        } else {
            merged.push(a[r]);
            r += 1;
        }
    }
    merged.extend_from_slice(&a[l..=left.hi]);
    merged.extend_from_slice(&a[r..=right.hi]);
    a[lo..=hi].copy_from_slice(&merged);
    PowerRun { lo, hi, power: 0 }
}

fn prepare_power_run(a: &mut [usize], start: usize, min_run: usize) -> usize {
    let n = a.len();
    let mut i = start + 1;
    if i < n && a[i - 1] > a[i] {
        while i < n && a[i - 1] > a[i] {
            i += 1;
        }
        a[start..i].reverse();
    } else {
        while i < n && a[i - 1] <= a[i] {
            i += 1;
        }
    }
    let end = (start + min_run).min(n).max(i);
    insertion_sort(&mut a[start..end]);
    end
}

fn power_sort(a: &mut [usize]) {
    const MIN_RUN: usize = 32;
    let n = a.len();
    if n <= 1 {
        return;
    }
    let mut stack: Vec<PowerRun> = Vec::new();
    let mut b1 = 0usize;
    let mut e1 = prepare_power_run(a, 0, MIN_RUN);
    while e1 < n {
        let b2 = e1;
        let e2 = prepare_power_run(a, b2, MIN_RUN);
        let p = node_power(n, b1, e1, b2, e2);
        while stack.last().is_some_and(|top| top.power > p) {
            let top = stack.pop().unwrap();
            let cur = PowerRun {
                lo: b1,
                hi: e1 - 1,
                power: 0,
            };
            let merged = merge_power_runs(a, top, cur);
            b1 = merged.lo;
            e1 = merged.hi + 1;
        }
        stack.push(PowerRun {
            lo: b1,
            hi: e1 - 1,
            power: p,
        });
        b1 = b2;
        e1 = e2;
    }
    while let Some(top) = stack.pop() {
        let cur = PowerRun {
            lo: b1,
            hi: e1 - 1,
            power: 0,
        };
        let merged = merge_power_runs(a, top, cur);
        b1 = merged.lo;
        e1 = merged.hi + 1;
    }
}

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

    power_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