イントロソートで配列を並び替える

イントロソートを使用する

イントロソート (introspective sort) は、クイックソートを主役にしつつ、再帰が深くなりすぎたらヒープソートに切り替え、さらに 十分に短い部分配列では挿入ソート で仕上げる、現実的な ハイブリッド整列 である。

David R. Musser が 1997 年に提案し、最悪時間計算量を O(n log n) に保ちながら、平均的にはクイックソートに近い速度を狙える。

クイックソート単体は入力次第でピボット選びが偏り、再帰深度が O(n) になり 最悪 O(n²) になり得る。

イントロソートは 許容する再帰の深さに上限（多くの実装で 2·⌊log₂ n⌋ 前後）を設け、それを超えそうな区間だけヒープソートにフォールバックすることで、比較ソートとしての下界 Ω(n log n) に張り付いたまま、最悪ケースを回避する。

クイックソート: 通常どおり分割と再帰を行う。
深さの監視: 再帰の残り許容深度が 0 になった区間は、クイックソートを続けず ヒープソート で処理する。
小区間の挿入: 要素数が閾値以下の部分配列は 挿入ソート で済ませる（再帰オーバーヘッドとマージコストを抑える）。

procedure introsort(A, lo, hi, depth_limit)
  if hi - lo <= INSERTION_THRESHOLD then
    insertion_sort(A, lo, hi)
    return
  if depth_limit = 0 then
    heapsort(A, lo, hi)
    return
  p = partition(A, lo, hi)
  introsort(A, lo, p - 1, depth_limit - 1)
  introsort(A, p + 1, hi, depth_limit - 1)

procedure sort(A)
  introsort(A, 0, length(A) - 1, max(2 * floor(log2(length(A))), 1))

全体として 比較による最悪時間計算量は O(n log n)（ヒープソート区間が支配的になりうる）、追加メモリは実装次第だがヒープソート部分で O(1) のインプレース志向を保ちやすい。安定ソートではない 場合が多い（ピボット型の分割・挿入ソートの交換が相対順序を変えうる）。

C++ の std::sort や、一部言語ランタイムの汎用ソートが、クイックソート系＋フォールバックという構成をとることがある。バブルソートのように単純な比較ソートと対比すると、「平均の速さ」と「最悪保証」を両立する設計意図が把握しやすい。

以下のデモでは 閾値・深さ計算を実装と揃えたうえで、オレンジは比較、緑は交換、紫は確定したピボット、青系は挿入ソート中の強調、ヒープフェーズ開始時はキャプションで明示する。昇順に近いデータではクイックソートの分割が偏りやすく、ヒープソートへの切り替え が現れやすい。

ピボット選択や閾値、切片アルゴリズムは実装ごとに異なるが、「高速な平均ケースとしてのクイックソート」と「保証された最悪効率としてのヒープソート」を組み合わせるという発想は、整列アルゴリズムを実務レベルへ押し上げる典型的な一手である。

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

Size	Average time	Maximum time	Average memory	Maximum memory
256	0.000005	0.000631	1661	1668
512	0.000012	0.000033	1665	1672
1024	0.000026	0.000644	1674	1680
2048	0.000058	0.000668	1690	1696
4096	0.000124	0.000520	1722	1728
8192	0.000269	0.000598	1785	1792
16384	0.000581	0.000873	1917	1924
32768	0.001255	0.001718	2178	2184
65536	0.002758	0.009310	2689	2696
131072	0.005840	0.019221	3714	3720
262144	0.012282	0.031689	5761	5768

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

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 partition_at(a: &mut [usize], lo: usize, hi: usize, pivot_idx: usize) -> usize {
    a.swap(pivot_idx, hi);
    let pivot = a[hi];
    let mut i = lo;
    for j in lo..hi {
        if a[j] < pivot {
            a.swap(i, j);
            i += 1;
        }
    }
    a.swap(i, hi);
    i
}
fn partition(a: &mut [usize], lo: usize, hi: usize) -> usize {
    partition_at(a, lo, hi, lo + (hi - lo) / 2)
}
fn sift_down(a: &mut [usize], mut root: usize, end: usize) {
    loop {
        let child = root * 2 + 1;
        if child > end {
            break;
        }
        let mut swap_idx = child;
        if child < end && a[child] < a[child + 1] {
            swap_idx = child + 1;
        }
        if a[root] >= a[swap_idx] {
            break;
        }
        a.swap(root, swap_idx);
        root = swap_idx;
    }
}

fn heap_sort(a: &mut [usize]) {
    if a.len() <= 1 {
        return;
    }
    for start in (0..a.len() / 2).rev() {
        sift_down(a, start, a.len() - 1);
    }
    for end in (1..a.len()).rev() {
        a.swap(0, end);
        sift_down(a, 0, end - 1);
    }
}
fn intro_sort_range(a: &mut [usize], lo: usize, hi: usize, depth: usize) {
    if hi <= lo {
        return;
    }
    if hi - lo < 16 {
        insertion_sort(&mut a[lo..=hi]);
        return;
    }
    if depth == 0 {
        heap_sort(&mut a[lo..=hi]);
        return;
    }
    let p = partition(a, lo, hi);
    if p > 0 {
        intro_sort_range(a, lo, p - 1, depth - 1);
    }
    intro_sort_range(a, p + 1, hi, depth - 1);
}

fn intro_sort(a: &mut [usize]) {
    if let Some(hi) = a.len().checked_sub(1) {
        let depth = usize::BITS as usize - a.len().leading_zeros() as usize;
        intro_sort_range(a, 0, hi, depth * 2);
    }
}

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

    intro_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