トーナメントソートで配列を並び替える

トーナメントソートを使用する

トーナメントソート (tournament sort) は、配列の各要素を葉とする完全二分木を用意し、隣接する葉同士の比較で「勝者」（昇順なら小さい方のインデックス）を親へ伝播させる トーナメント木 を構築する比較ソートである。根には常に未処理領域の最小要素の位置が残るため、最小を1つ取り出すたびに根から葉へ向かって木だけを更新すればよく、毎回配列全体を走査する選択ソートより比較回数を抑えられる。

木の準備: 要素数 n 以上の2の冪 k の葉を持つ配列 tree を用意する。葉 tree[k+i] にはインデックス i（i ≥ n の余りは無効）を入れる。
構築: 葉から根へ向かい、各内部ノードに左右の子の勝者インデックスを記録する。
抽出: 根 tree[1] が示すインデックスの値を出力位置へ書き出し、その葉を無効化する（比較から外す）。
更新: 無効化した葉から親へ遡り、各内部ノードの勝者を再計算する。
繰り返し: n 回手順3〜4を行えば昇順に整列する。

procedure tournament_sort(A)
  n = length(A)
  k = smallest power of 2 with k >= n
  build tree leaves with indices 0 .. k-1 (padding invalid)
  for i from k-1 down to 1
    tree[i] = winner(A, tree[2i], tree[2i+1])
  for pos from 0 to n - 1
    idx = tree[1]
    output[pos] = A[idx]
    mark A[idx] as removed (sentinel)
    update tree along path from leaf k + idx to root
  copy output back into A

winner は無効葉を飛ばし、有効な2インデックスのうち値が小さい方を返す。構築に O(n)、各抽出の更新に O(log n) かかるため、全体で比較回数は O(n log n) 程度になる。

木用の補助配列に O(n) の追加領域が必要で、同一キーの相対順序を保たない 不安定 なソートとして扱われることが多い。

外部ソートの 置換選択（replacement selection）で「次に小さいレコード」を繰り返し取り出す構造と同型であり、ディスク上の連続ブロックから順位を決める場面で名前がよく登場する。

選択ソートのように「毎回最小を1つ確定する」流れは同じだが、最小の探索を木で共有するため漸近的には有利になりやすい。一方で補助配列と更新処理の分、小さな n では定数倍で負けることもある。

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

Size	Average time	Maximum time	Average memory	Maximum memory
256	0.000014	0.000448	1670	1676
512	0.000028	0.000865	1678	1684
1024	0.000052	0.000292	1698	1704
2048	0.000109	0.001297	1738	1744
4096	0.000237	0.000934	1818	1824
8192	0.000535	0.004348	1849	1856
16384	0.001211	0.004490	2048	2048
32768	0.002568	0.006344	2688	2688
65536	0.005691	0.039156	3967	3968
131072	0.013399	0.067338	6528	6528
262144	0.031101	0.575988	11765	11768

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

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 tournament_winner(a: &[usize], left: usize, right: usize) -> usize {
    if left == usize::MAX {
        return right;
    }
    if right == usize::MAX {
        return left;
    }
    if a[left] <= a[right] {
        left
    } else {
        right
    }
}

fn tournament_sort(a: &mut [usize]) {
    let n = a.len();
    if n <= 1 {
        return;
    }
    let k = n.next_power_of_two();
    let mut tree = vec![0usize; 2 * k];
    for i in 0..k {
        tree[k + i] = if i < n { i } else { usize::MAX };
    }
    for i in (1..k).rev() {
        tree[i] = tournament_winner(a, tree[2 * i], tree[2 * i + 1]);
    }
    let mut out = vec![0usize; n];
    for pos in 0..n {
        let idx = tree[1];
        out[pos] = a[idx];
        a[idx] = usize::MAX;
        let mut node = k + idx;
        tree[node] = usize::MAX;
        while node > 1 {
            node /= 2;
            tree[node] = tournament_winner(a, tree[2 * node], tree[2 * node + 1]);
        }
    }
    a.copy_from_slice(&out);
}

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

    tournament_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