ティムソートで配列を並び替える

ティムソートを使用する

ティムソート (Timsort) は、マージソートの分割・併合の枠組みに、すでに整列している連続区間（ラン）を活かす仕組みと、短いランを伸ばす挿入ソートを組み合わせたハイブリッドアルゴリズムである。Python の list.sort() 向けに設計された。

ランの検出: 配列を左から走査し、昇順または厳密な降順の連続区間（ラン）を見つける。降順ランはその場で反転し、昇順ランにそろえる。
ランの拡張: ランの長さが最小ラン長未満なら、二分探索付き挿入ソートで最小ラン長まで（または配列末尾まで）伸ばす。最小ラン長は配列長から計算され、おおむね 32〜64 付近になる（デモでは見やすさのため 4 に固定している）。
スタックへの積み上げ: 整えたランを (開始, 長さ) としてスタックにプッシュする。
マージの抑制: プッシュのたびに、スタック上のラン長のバランスを見て隣接ランをマージする。最後に残ったランをすべて併合して全体を整列する。

procedure timsort(A)
  n = length(A)
  minRun = compute_min_run(n)
  stack = empty list of runs
  i = 0
  while i < n
    runLen = count_run(A, i)
    if A[i .. i+runLen-1] is descending then
      reverse(A, i, i + runLen - 1)
    if runLen < minRun then
      extend_run_with_insertion(A, i, min(i + minRun, n) - 1)
      runLen = min(minRun, n - i)
    push stack with (i, runLen)
    merge_collapse(stack, A)
    i = i + runLen
  merge_force_collapse(stack, A)

マージ自体はマージソートと同様に 2 本の昇順列の先頭を比較しながら確定させる。実装ではガロップ（一方の列が連続して勝つときにまとめて取り込む）などの最適化も入るが、デモでは基本的な 2 路マージまでを追えるようにしている。

最悪時間計算量は O(n log n) ですでに昇順に近い入力ではランが長く取れ、最良は O(n) に近づく。補助領域はマージ用に O(n) が必要になることが多く、安定ソートである。

クイックソートのように最悪 O(n²) に落ちにくく、マージソートのように安定で O(n log n) を保てる点が強みである。

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

Size	Average time	Maximum time	Average memory	Maximum memory
256	0.000006	0.000613	1666	1672
512	0.000013	0.000466	1674	1680
1024	0.000030	0.000408	1686	1692
2048	0.000066	0.000620	1714	1720
4096	0.000143	0.000760	1757	1764
8192	0.000316	0.001064	1858	1864
16384	0.000700	0.002439	1990	1996
32768	0.001518	0.004154	2454	2460
65536	0.003306	0.007707	3327	3328
131072	0.006967	0.009603	5170	5176
262144	0.014977	0.143042	8819	8824

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

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 tim_sort(a: &mut [usize]) {
    const MIN_RUN: usize = 32;
    let n = a.len();
    let mut runs = Vec::new();
    let mut i = 0;
    while i < n {
        let start = i;
        i += 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]);
        runs.push((start, end));
        i = end;
    }
    while runs.len() > 1 {
        let mut next = Vec::new();
        for pair in runs.chunks(2) {
            if pair.len() == 1 {
                next.push(pair[0]);
                continue;
            }
            let (lo, mid) = pair[0];
            let (_, hi) = pair[1];
            let mut merged = Vec::with_capacity(hi - lo);
            let (mut l, mut r) = (lo, mid);
            while l < mid && r < 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..mid]);
            merged.extend_from_slice(&a[r..hi]);
            a[lo..hi].copy_from_slice(&merged);
            next.push((lo, hi));
        }
        runs = next;
    }
}

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

    tim_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