コタソートで配列を並び替える

コタソートを使用する

コタソート（KotaSort）はボトムアップのマージソートの枠組みの中で、長さ O(√n) 程度のブロック単位で併合し、併合のあとにブロック選択ソートでブロックの順序を整える比較ソートである。

グレイルソートが併合前にブロック選択を行い、ウィキソートが併合と同時にブロック選択を行うのに対し、コタソートは併合後にブロック選択を行う。ブロックマージのロジックが最も単純で実装しやすく、移動回数と併合比較が最適化されている。多方向ブロックマージへの一般化も可能である。

小さなラン整列: 長さ 16 程度以下の区間は挿入ソートで整える。
ボトムアップ併合: 隣接する整列済み部分列を段階的に倍化しながらマージする。
ブロック併合: 区間が十分大きくなると、長さ √n 程度のブロックに分割し、外部バッファを使って隣接ブロックを順にマージする。
ブロック選択: マージが終わったブロック列に対し、各ブロックの先頭要素をキーとして選択ソートを行い、ブロック全体の順序を決める。安定性のため、別のキーバッファでブロックの元の相対順序を追跡する。
キーの復元: 収集した一意なキー列（約 3√n 個）を挿入ソートし、全体へマージして整列を完了する。

procedure kota_sort(A)
  if length(A) < 16 then
    insertion_sort(A)
    return
  block_len = floor(sqrt(length(A)))
  keys = collect_unique_keys(A, about 3 * block_len)
  build_sorted_runs_bottom_up(A, block_len)
  level = block_len
  while level < length(A)
    for each adjacent pair of sorted runs of length level
      merge_blocks_with_buffer(A, block_len, buffer)
      block_select_sort(A, keys, block_len)   // Kota: selection after merge
    level = level * 2
  insertion_sort(keys)
  merge keys back into A

コタソートはバッファレス変種を持たないため、配列全体を完結させるには別のブロックマージソート（グレイルソートやウィキソートなど）との組み合わせが必要になる。キー数は他のブロックマージ変種と比べて最も多く、約 3√n 個を要する。

最悪時間計算量は O(n log n) で、追加空間は外部バッファを用いる変種では O(√n) 程度となる。安定ソートである。

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

Size	Average time	Maximum time	Average memory	Maximum memory
256	0.000006	0.000515	1666	1672
512	0.000012	0.000707	1669	1676
1024	0.000027	0.000476	1677	1684
2048	0.000062	0.000437	1698	1704
4096	0.000135	0.000481	1737	1744
8192	0.000296	0.000599	1821	1828
16384	0.000640	0.001047	1986	1992
32768	0.001386	0.003197	2306	2312
65536	0.003019	0.003812	2820	2824
131072	0.006439	0.012326	4096	4096
262144	0.014072	0.023600	6659	6768

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

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 kota_insertion_sort(a: &mut [usize], lo: usize, hi: usize) {
    for i in lo + 1..hi {
        let key = a[i];
        let mut j = i;
        while j > lo && a[j - 1] > key {
            a[j] = a[j - 1];
            j -= 1;
        }
        a[j] = key;
    }
}

fn kota_block_swap(a: &mut [usize], start: usize, block_len: usize, i: usize, j: usize) {
    let bi = start + i * block_len;
    let bj = start + j * block_len;
    for k in 0..block_len {
        a.swap(bi + k, bj + k);
    }
}

fn kota_block_select(a: &mut [usize], start: usize, block_count: usize, block_len: usize) {
    for i in 0..block_count {
        let mut min = i;
        for j in i + 1..block_count {
            if a[start + j * block_len] < a[start + min * block_len] {
                min = j;
            }
        }
        if min != i {
            kota_block_swap(a, start, block_len, i, min);
        }
    }
}

fn kota_merge_with_buffer(a: &mut [usize], lo: usize, mid: usize, hi: usize, buf: &mut Vec<usize>) {
    let left_len = mid - lo;
    buf.resize(left_len, 0);
    buf[..left_len].copy_from_slice(&a[lo..mid]);
    let mut i = 0usize;
    let mut j = mid;
    let mut k = lo;
    while i < left_len && j < hi {
        if buf[i] <= a[j] {
            a[k] = buf[i];
            i += 1;
        } else {
            a[k] = a[j];
            j += 1;
        }
        k += 1;
    }
    while i < left_len {
        a[k] = buf[i];
        i += 1;
        k += 1;
    }
}

fn kota_sort(a: &mut [usize]) {
    let n = a.len();
    if n <= 1 {
        return;
    }

    let run_size = 16usize;
    let block_len = (n as f64).sqrt() as usize;
    let block_len = block_len.max(1);

    if n < run_size {
        kota_insertion_sort(a, 0, n);
        return;
    }

    for start in (0..n).step_by(run_size) {
        let end = (start + run_size).min(n);
        kota_insertion_sort(a, start, end);
    }

    let mut merge_buf = Vec::new();
    let mut width = run_size;
    while width < n {
        for lo in (0..n).step_by(width * 2) {
            let mid = (lo + width).min(n);
            let hi = (lo + width * 2).min(n);
            if mid >= hi {
                continue;
            }
            kota_merge_with_buffer(a, lo, mid, hi, &mut merge_buf);
            let span = hi - lo;
            if span >= block_len * 2 {
                let block_count = span / block_len;
                kota_block_select(a, lo, block_count, block_len);
            }
        }
        width *= 2;
    }
}

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

    kota_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