ストランドソートで配列を並び替える

ストランドソートを使用する

ストランドソート (strand sort) は、未整列の区間を左から一度走査し、先頭から続く単調非減少部分列（ストランド）だけを抜き取り、それをすでに得られている整列済みの結果と マージ（併合） することを繰り返す比較ソートである。「麻ひも・繊維束（strand）をほどく」イメージで、1 本のストランドをずつ取り出して束ね直していく。

初期化: 整列済み結果 R は空、P に入力をそのまま置く。
ストランド抽出: P を左から見て、直前にストランドへ入れた末尾の値以上の要素だけを順にストランドへ移す（末尾より小さい値は見送り、インデックスだけ進める）。1 回の走査でストランドは必ず 1 要素以上になる。
マージ: R とストランドはどちらも昇順なので、マージソートと同様に先頭同士を比較しながら併合し、新しい R とする。P に残った要素はそのまま次のラウンドへ。
終了: P が空になるまで手順 2〜3 を繰り返す。

最悪では 1 要素ずつしかストランドが伸びず、マージは合計で O(n²) 相当になる。マージを安定に実装（同値では常に R 側を先に取るなど）すれば、全体も安定ソートにできる。ストランドの取り出しとマージの双方で 追加配列 を使う実装が一般的で、空間計算量は実装次第だが O(n) 程度を要しやすい。

procedure strand_sort(input)
  R = empty list
  P = copy of input
  while P is not empty
    strand = empty list
    i = 0
    while i < length(P)
      if strand is empty or P[i] >= last(strand) then
        append P[i] to strand
        remove P[i] from P
      else
        i = i + 1
    R = merge(R, strand) // both sorted; stable if merge breaks ties toward R
  return R

一般用途の標準ソートとしてはクイックソートやティムソートなどに比べ不利になりやすい。マージソートと対比するとマージの性質の理解が進みやすい。

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

Size	Average time	Maximum time	Average memory	Maximum memory
256	0.000020	0.000417	1695	1712
512	0.000038	0.000336	1707	1724
1024	0.000077	0.000439	1731	1752
2048	0.000164	0.000556	1778	1812
4096	0.000387	0.000698	1874	1928
8192	0.001060	0.004150	2002	2116
16384	0.003168	0.004307	2294	2512
32768	0.008888	0.030573	3023	3460
65536	0.025005	0.050163	4465	5376
131072	0.073710	0.230847	7334	8968
262144	0.215601	0.473105	13019	16384

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

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 merge_values(left: &[usize], right: &[usize]) -> Vec<usize> {
    let mut out = Vec::with_capacity(left.len() + right.len());
    let (mut l, mut r) = (0, 0);
    while l < left.len() && r < right.len() {
        if left[l] <= right[r] {
            out.push(left[l]);
            l += 1;
        } else {
            out.push(right[r]);
            r += 1;
        }
    }
    out.extend_from_slice(&left[l..]);
    out.extend_from_slice(&right[r..]);
    out
}
fn strand_sort(a: &mut [usize]) {
    let mut input = a.to_vec();
    let mut output = Vec::new();
    while !input.is_empty() {
        let mut strand = Vec::new();
        let mut rest = Vec::new();
        for value in input {
            if strand.last().map_or(true, |last| *last <= value) {
                strand.push(value);
            } else {
                rest.push(value);
            }
        }
        output = merge_values(&output, &strand);
        input = rest;
    }
    a.copy_from_slice(&output);
}

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

    strand_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