オクトソートで配列を並び替える

#!/usr/bin/env swift
import Foundation

// This standalone Swift driver creates the same temporary Docker build
// context as the former shell wrapper.  The benchmark program itself remains
// embedded below so readers can copy one complete, reproducible file.
struct BenchmarkError: Error, CustomStringConvertible {
    let message: String

    var description: String { message }

    init(_ message: String) {
        self.message = message
    }
}

func runCommand(_ executable: String, _ arguments: [String]) throws {
    let process = Process()
    process.executableURL = URL(fileURLWithPath: "/usr/bin/env")
    process.arguments = [executable] + arguments
    process.standardInput = FileHandle.standardInput
    process.standardOutput = FileHandle.standardOutput
    process.standardError = FileHandle.standardError

    do {
        try process.run()
    } catch {
        throw BenchmarkError("Could not start \(executable): \(error)")
    }
    process.waitUntilExit()
    guard process.terminationStatus == 0 else {
        throw BenchmarkError(
            "Command failed (\(process.terminationStatus)): " +
            "\(executable) \(arguments.joined(separator: " "))"
        )
    }
}

do {
    // The UUID avoids collisions when two benchmark copies are run at once.
    let workdir = FileManager.default.temporaryDirectory
        .appendingPathComponent("swift-sort-benchmark-\(UUID().uuidString)")
    try FileManager.default.createDirectory(at: workdir, withIntermediateDirectories: true)
    defer { try? FileManager.default.removeItem(at: workdir) }

    // A raw Swift string is used so the nested main.swift keeps its own
    // interpolation expressions such as \(seed) until Docker compiles it.
    let dockerfile = #"""
FROM swift:6.0

WORKDIR /app

RUN cat > alloc_track.c <<'ALLOC'
#define _GNU_SOURCE
#include <dlfcn.h>
#include <malloc.h>
#include <stdatomic.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

static atomic_size_t live_bytes = 0;
static atomic_size_t peak_bytes = 0;

static void *(*real_malloc)(size_t) = NULL;
static void *(*real_calloc)(size_t, size_t) = NULL;
static void *(*real_realloc)(void *, size_t) = NULL;
static void (*real_free)(void *) = NULL;

static void init_reals(void) {
    if (real_malloc) {
        return;
    }
    real_malloc = (void *(*)(size_t))dlsym(RTLD_NEXT, "malloc");
    real_calloc = (void *(*)(size_t, size_t))dlsym(RTLD_NEXT, "calloc");
    real_realloc = (void *(*)(void *, size_t))dlsym(RTLD_NEXT, "realloc");
    real_free = (void (*)(void *))dlsym(RTLD_NEXT, "free");
}

static void record_alloc(size_t size) {
    size_t live = atomic_fetch_add(&live_bytes, size) + size;
    size_t peak = atomic_load(&peak_bytes);
    while (live > peak) {
        if (atomic_compare_exchange_weak(&peak_bytes, &peak, live)) {
            break;
        }
    }
}

void alloc_track_reset_peak(void) {
    atomic_store(&peak_bytes, atomic_load(&live_bytes));
}

size_t alloc_track_live(void) { return atomic_load(&live_bytes); }
size_t alloc_track_peak(void) { return atomic_load(&peak_bytes); }

void *malloc(size_t size) {
    init_reals();
    void *p = real_malloc(size);
    if (p) {
        record_alloc(malloc_usable_size(p));
    }
    return p;
}

void *calloc(size_t nmemb, size_t size) {
    init_reals();
    void *p = real_calloc(nmemb, size);
    if (p) {
        record_alloc(malloc_usable_size(p));
    }
    return p;
}

void *realloc(void *ptr, size_t size) {
    init_reals();
    size_t old_size = 0;
    if (ptr) {
        old_size = malloc_usable_size(ptr);
    }
    void *p = real_realloc(ptr, size);
    if (p) {
        atomic_fetch_sub(&live_bytes, old_size);
        record_alloc(malloc_usable_size(p));
    } else if (size == 0) {
        atomic_fetch_sub(&live_bytes, old_size);
    }
    return p;
}

void free(void *ptr) {
    init_reals();
    if (ptr) {
        atomic_fetch_sub(&live_bytes, malloc_usable_size(ptr));
        real_free(ptr);
    }
}

ALLOC

RUN cat > main.swift <<'SWIFT'
import Foundation
#if canImport(Glibc)
import Glibc
#elseif canImport(Darwin)
import Darwin
#endif

@_silgen_name("alloc_track_live") func alloc_track_live() -> Int
@_silgen_name("alloc_track_peak") func alloc_track_peak() -> Int
@_silgen_name("alloc_track_reset_peak") func alloc_track_reset_peak()

extension UnsafeMutableBufferPointer where Element == Int {
    func swapAt(_ i: Int, _ j: Int) {
        let t = self[i]; self[i] = self[j]; self[j] = t
    }
}

let MIN_POWER: Int = 8
let MAX_POWER: Int = 18
let RUNS: Int = 8192


/// Educational stand-in for scandum's octosort (WikiSort + quadsort ideas).
/// Production uses block tagging for large in-place merges; here levels that
/// exceed the fixed cache use monobound search + Gries–Mills rotation so
/// auxiliary memory stays O(1). Reverse runs are handled by the octo swap.

fileprivate let OCTO_CACHE = 512

fileprivate struct OctoRange {
    var start: Int
    var end: Int

    init(_ start: Int, _ end: Int) {
        self.start = start
        self.end = end
    }

    var len: Int { end - start }
}

fileprivate final class OctoIterator {
    var size: Int
    var power_of_two: Int
    var numerator: Int
    var decimal: Int
    var denominator: Int
    var decimal_step: Int
    var numerator_step: Int

    init(_ size: Int, _ min_level: Int) {
        let power_of_two = octo_floor_power_of_two(size)
        let denominator = power_of_two / min_level
        self.size = size
        self.power_of_two = power_of_two
        self.numerator = 0
        self.decimal = 0
        self.denominator = denominator
        self.decimal_step = size / denominator
        self.numerator_step = size % denominator
    }

    func begin() {
        numerator = 0
        decimal = 0
    }

    func next_range() -> OctoRange {
        let start = decimal
        decimal += decimal_step
        numerator += numerator_step
        if numerator >= denominator {
            numerator -= denominator
            decimal += 1
        }
        return OctoRange(start, decimal)
    }

    func finished() -> Bool {
        decimal >= size
    }

    func next_level() -> Bool {
        decimal_step += decimal_step
        numerator_step += numerator_step
        if numerator_step >= denominator {
            numerator_step -= denominator
            decimal_step += 1
        }
        return decimal_step < size
    }

    func length() -> Int {
        decimal_step
    }
}

fileprivate func octo_floor_power_of_two(_ value: Int) -> Int {
    var x = value
    x |= x >> 1
    x |= x >> 2
    x |= x >> 4
    x |= x >> 8
    x |= x >> 16
    x |= x >> 32
    return x - (x >> 1)
}

fileprivate func octo_copy_within(
    _ a: UnsafeMutableBufferPointer<Int>,
    _ src: Range<Int>,
    _ dest: Int
) {
    let n = src.count
    guard n > 0, let base = a.baseAddress else { return }
    memmove(
        base.advanced(by: dest),
        base.advanced(by: src.lowerBound),
        n * MemoryLayout<Int>.stride
    )
}

fileprivate func octo_insertion_sort(_ a: UnsafeMutableBufferPointer<Int>, _ range: OctoRange) {
    for i in (range.start + 1)..<range.end {
        let temp = a[i]
        var j = i
        while j > range.start && temp < a[j - 1] {
            a[j] = a[j - 1]
            j -= 1
        }
        a[j] = temp
    }
}

fileprivate func octo_tail_insert(_ a: UnsafeMutableBufferPointer<Int>, _ start: Int, _ i: Int) {
    let temp = a[i]
    var j = i
    while j > start && temp < a[j - 1] {
        a[j] = a[j - 1]
        j -= 1
    }
    a[j] = temp
}

/// Sorting network for four keys (stable for equals via `>`).
fileprivate func octo_swap4(
    _ a: UnsafeMutableBufferPointer<Int>,
    _ i0: Int,
    _ i1: Int,
    _ i2: Int,
    _ i3: Int
) {
    if a[i0] > a[i1] {
        a.swapAt(i0, i1)
    }
    if a[i2] > a[i3] {
        a.swapAt(i2, i3)
    }
    if a[i0] > a[i2] {
        a.swapAt(i0, i2)
    }
    if a[i1] > a[i3] {
        a.swapAt(i1, i3)
    }
    if a[i1] > a[i2] {
        a.swapAt(i1, i2)
    }
}

fileprivate func octo_is_reverse4(_ a: UnsafeMutableBufferPointer<Int>, _ start: Int) -> Bool {
    a[start] > a[start + 1]
        && a[start + 2] > a[start + 3]
        && a[start + 1] > a[start + 2]
}

fileprivate func octo_range_nonincreasing(
    _ a: UnsafeMutableBufferPointer<Int>,
    _ range: OctoRange
) -> Bool {
    for i in (range.start + 1)..<range.end {
        if a[i - 1] < a[i] {
            return false
        }
    }
    return true
}

/// Educational octo swap over a WikiIterator run (length 4..=8).
/// `rev_start` is the start of an unfinished reverse run; returns an updated
/// reverse-run start, or `nil` when no reverse run is pending.
fileprivate func octo_swap(
    _ a: UnsafeMutableBufferPointer<Int>,
    _ range: OctoRange,
    _ rev_start: Int?
) -> Int? {
    let start = range.start
    let len = range.len
    if len == 0 {
        return rev_start
    }
    if len < 4 {
        if let rs = rev_start {
            var i = rs
            var j = start - 1
            while i < j {
                a.swapAt(i, j)
                i += 1
                j -= 1
            }
        }
        octo_insertion_sort(a, range)
        return nil
    }

    let can_extend_reverse = rev_start == nil
        || (start > 0 && a[start - 1] >= a[start])

    if octo_is_reverse4(a, start)
        && can_extend_reverse
        && octo_range_nonincreasing(a, range)
    {
        return rev_start ?? start
    }

    if let rs = rev_start {
        var i = rs
        var j = start - 1
        while i < j {
            a.swapAt(i, j)
            i += 1
            j -= 1
        }
    }

    if octo_is_reverse4(a, start) {
        a.swapAt(start, start + 3)
        a.swapAt(start + 1, start + 2)
    } else {
        octo_swap4(a, start, start + 1, start + 2, start + 3)
    }
    for i in (start + 4)..<range.end {
        octo_tail_insert(a, start, i)
    }
    return nil
}

fileprivate func octo_reverse_range(_ a: UnsafeMutableBufferPointer<Int>, _ range: OctoRange) {
    let len = range.len
    for index in 0..<(len / 2) {
        a.swapAt(range.start + index, range.end - index - 1)
    }
}

fileprivate func octo_swap_blocks(
    _ a: UnsafeMutableBufferPointer<Int>,
    _ left: Int,
    _ right: Int,
    _ n: Int
) {
    for i in 0..<n {
        a.swapAt(left + i, right + i)
    }
}

/// Gries–Mills rotation via block swaps (cache-assisted when a side fits).
fileprivate func octo_rotate(
    _ a: UnsafeMutableBufferPointer<Int>,
    _ amount: Int,
    _ range: OctoRange,
    _ cache: UnsafeMutableBufferPointer<Int>,
    _ cache_size: Int
) {
    if range.len == 0 || amount == 0 || amount == range.len {
        return
    }
    let split = range.start + amount
    let left_len = amount
    let right_len = range.len - amount

    if left_len <= right_len {
        if left_len <= cache_size {
            for i in 0..<left_len {
                cache[i] = a[range.start + i]
            }
            octo_copy_within(a, split..<range.end, range.start)
            for i in 0..<left_len {
                a[range.start + right_len + i] = cache[i]
            }
            return
        }
    } else if right_len <= cache_size {
        for i in 0..<right_len {
            cache[i] = a[split + i]
        }
        octo_copy_within(a, range.start..<split, range.start + right_len)
        for i in 0..<right_len {
            a[range.start + i] = cache[i]
        }
        return
    }

    // Gries–Mills: swap equal-sized blocks until the two sides balance.
    var i = left_len
    var j = right_len
    let mid = split
    while i != j {
        if i > j {
            octo_swap_blocks(a, mid - i, mid, j)
            i -= j
        } else {
            octo_swap_blocks(a, mid - i, mid + j - i, i)
            j -= i
        }
    }
    octo_swap_blocks(a, mid - i, mid, i)
}

fileprivate func octo_merge_into(
    _ from: UnsafeBufferPointer<Int>,
    _ a: OctoRange,
    _ b: OctoRange,
    _ into: UnsafeMutableBufferPointer<Int>
) {
    var a_index = a.start
    var b_index = b.start
    var insert = 0
    while true {
        if from[b_index] >= from[a_index] {
            into[insert] = from[a_index]
            a_index += 1
            insert += 1
            if a_index == a.end {
                for k in 0..<(b.end - b_index) {
                    into[insert + k] = from[b_index + k]
                }
                break
            }
        } else {
            into[insert] = from[b_index]
            b_index += 1
            insert += 1
            if b_index == b.end {
                for k in 0..<(a.end - a_index) {
                    into[insert + k] = from[a_index + k]
                }
                break
            }
        }
    }
}

fileprivate func octo_merge_into_mut(
    _ from: UnsafeMutableBufferPointer<Int>,
    _ a: OctoRange,
    _ b: OctoRange,
    _ into: UnsafeMutableBufferPointer<Int>
) {
    octo_merge_into(UnsafeBufferPointer(from), a, b, into)
}

fileprivate func octo_merge_external(
    _ a: UnsafeMutableBufferPointer<Int>,
    _ a_range: OctoRange,
    _ b: OctoRange,
    _ cache: UnsafeMutableBufferPointer<Int>
) {
    for i in 0..<a_range.len {
        cache[i] = a[a_range.start + i]
    }
    var a_index = 0
    var b_index = b.start
    var insert = a_range.start
    let a_last = a_range.len
    let b_last = b.end
    if b.len > 0 && a_range.len > 0 {
        while true {
            if a[b_index] >= cache[a_index] {
                a[insert] = cache[a_index]
                a_index += 1
                insert += 1
                if a_index == a_last {
                    break
                }
            } else {
                a[insert] = a[b_index]
                b_index += 1
                insert += 1
                if b_index == b_last {
                    break
                }
            }
        }
    }
    for i in 0..<(a_last - a_index) {
        a[insert + i] = cache[a_index + i]
    }
}

/// Quadsort-style tail merge: right run fits in `cache`, merge backward.
fileprivate func octo_merge_external_right(
    _ a: UnsafeMutableBufferPointer<Int>,
    _ a_range: OctoRange,
    _ b: OctoRange,
    _ cache: UnsafeMutableBufferPointer<Int>
) {
    let right_len = b.len
    for i in 0..<right_len {
        cache[i] = a[b.start + i]
    }
    var i = a_range.end
    var j = right_len
    var k = b.end
    while i > a_range.start && j > 0 {
        if a[i - 1] > cache[j - 1] {
            k -= 1
            i -= 1
            a[k] = a[i]
        } else {
            k -= 1
            j -= 1
            a[k] = cache[j]
        }
    }
    while j > 0 {
        k -= 1
        j -= 1
        a[k] = cache[j]
    }
}

/// Monobound binary search: first offset in `a[start..start+length)` with
/// `a[i] >= target` (scandum monobound style).
fileprivate func octo_monobound_search_left(
    _ a: UnsafeMutableBufferPointer<Int>,
    _ start: Int,
    _ length: Int,
    _ target: Int
) -> Int {
    if length == 0 {
        return 0
    }
    var end = start + length
    var top = length
    while top > 1 {
        let mid = top / 2
        if target <= a[end - mid] {
            end -= mid
        }
        top -= mid
    }
    if target <= a[end - 1] {
        return end - 1 - start
    } else {
        return end - start
    }
}

fileprivate func octo_merge_in_place(
    _ a: UnsafeMutableBufferPointer<Int>,
    _ a_range: OctoRange,
    _ b: OctoRange,
    _ cache: UnsafeMutableBufferPointer<Int>,
    _ cache_size: Int
) {
    let left_len = a_range.len
    let right_len = b.len
    if left_len == 0 || right_len == 0 {
        return
    }
    if a[a_range.end - 1] <= a[b.start] {
        return
    }

    if left_len <= cache_size {
        octo_merge_external(a, a_range, b, cache)
        return
    }
    if right_len <= cache_size {
        octo_merge_external_right(a, a_range, b, cache)
        return
    }

    let rblock = left_len / 2
    let lblock = left_len - rblock
    let center = a[a_range.start + lblock]
    let left = octo_monobound_search_left(a, b.start, right_len, center)
    let right = right_len - left

    if left > 0 {
        octo_rotate(
            a,
            rblock,
            OctoRange(a_range.start + lblock, a_range.start + lblock + rblock + left),
            cache,
            cache_size
        )
        octo_merge_in_place(
            a,
            OctoRange(a_range.start, a_range.start + lblock),
            OctoRange(a_range.start + lblock, a_range.start + lblock + left),
            cache,
            cache_size
        )
        octo_merge_in_place(
            a,
            OctoRange(a_range.start + lblock + left, a_range.start + lblock + left + rblock),
            OctoRange(
                a_range.start + lblock + left + rblock,
                a_range.start + lblock + left + rblock + right
            ),
            cache,
            cache_size
        )
    } else if right > 0 {
        octo_merge_in_place(
            a,
            OctoRange(a_range.start + lblock, a_range.end),
            b,
            cache,
            cache_size
        )
    }
}

fileprivate func octo_merge_pair(
    _ a: UnsafeMutableBufferPointer<Int>,
    _ a_range: OctoRange,
    _ b: OctoRange,
    _ cache: UnsafeMutableBufferPointer<Int>,
    _ cache_size: Int
) {
    if a[b.end - 1] < a[a_range.start] {
        octo_rotate(
            a,
            a_range.len,
            OctoRange(a_range.start, b.end),
            cache,
            cache_size
        )
    } else if a[b.start] < a[a_range.end - 1] {
        if a_range.len <= cache_size {
            octo_merge_external(a, a_range, b, cache)
        } else {
            octo_merge_in_place(a, a_range, b, cache, cache_size)
        }
    }
}

func octo_sort(_ a: inout [Int]) {
    a.withUnsafeMutableBufferPointer { octo_sort($0) }
}

func octo_sort(_ a: UnsafeMutableBufferPointer<Int>) {
    let size = a.count
    var cacheStorage = [Int](repeating: 0, count: OCTO_CACHE)
    let cache_size = OCTO_CACHE

    cacheStorage.withUnsafeMutableBufferPointer { cache in
        if size < 4 {
            if size == 3 {
                if a[1] < a[0] {
                    a.swapAt(0, 1)
                }
                if a[2] < a[1] {
                    a.swapAt(1, 2)
                    if a[1] < a[0] {
                        a.swapAt(0, 1)
                    }
                }
            } else if size == 2 && a[1] < a[0] {
                a.swapAt(0, 1)
            }
            return
        }

        let iterator = OctoIterator(size, 4)
        iterator.begin()
        var rev_start: Int? = nil
        while !iterator.finished() {
            let range = iterator.next_range()
            rev_start = octo_swap(a, range, rev_start)
        }
        if let rs = rev_start {
            octo_reverse_range(a, OctoRange(rs, size))
            if rs == 0 {
                return
            }
        }
        if size < 8 {
            return
        }

        while true {
            if iterator.length() < cache_size {
                if (iterator.length() + 1) * 4 <= cache_size && iterator.length() * 4 <= size {
                    iterator.begin()
                    while !iterator.finished() {
                        let a1 = iterator.next_range()
                        let b1 = iterator.next_range()
                        let a2 = iterator.next_range()
                        let b2 = iterator.next_range()
                        var merged1_len = 0
                        var merged2_len = 0
                        if a[b1.end - 1] < a[a1.start] {
                            for i in 0..<a1.len {
                                cache[b1.len + i] = a[a1.start + i]
                            }
                            for i in 0..<b1.len {
                                cache[i] = a[b1.start + i]
                            }
                            merged1_len = a1.len + b1.len
                        } else if a[b1.start] < a[a1.end - 1] {
                            octo_merge_into_mut(a, a1, b1, cache)
                            merged1_len = a1.len + b1.len
                        } else if !(a[b2.start] < a[a2.end - 1]) && !(a[a2.start] < a[b1.end - 1]) {
                            continue
                        } else {
                            for i in 0..<a1.len {
                                cache[i] = a[a1.start + i]
                            }
                            for i in 0..<b1.len {
                                cache[a1.len + i] = a[b1.start + i]
                            }
                            merged1_len = a1.len + b1.len
                        }
                        let a1Merged = OctoRange(a1.start, b1.end)
                        if a[b2.end - 1] < a[a2.start] {
                            for i in 0..<a2.len {
                                cache[merged1_len + b2.len + i] = a[a2.start + i]
                            }
                            for i in 0..<b2.len {
                                cache[merged1_len + i] = a[b2.start + i]
                            }
                            merged2_len = a2.len + b2.len
                        } else if a[b2.start] < a[a2.end - 1] {
                            let into = UnsafeMutableBufferPointer(
                                rebasing: cache[merged1_len..<cache.count]
                            )
                            octo_merge_into_mut(a, a2, b2, into)
                            merged2_len = a2.len + b2.len
                        } else {
                            for i in 0..<a2.len {
                                cache[merged1_len + i] = a[a2.start + i]
                            }
                            for i in 0..<b2.len {
                                cache[merged1_len + a2.len + i] = a[b2.start + i]
                            }
                            merged2_len = a2.len + b2.len
                        }
                        let a3 = OctoRange(0, merged1_len)
                        let b3 = OctoRange(merged1_len, merged1_len + merged2_len)
                        if cache[b3.end - 1] < cache[a3.start] {
                            for i in 0..<merged1_len {
                                a[a1Merged.start + merged2_len + i] = cache[a3.start + i]
                            }
                            for i in 0..<merged2_len {
                                a[a1Merged.start + i] = cache[b3.start + i]
                            }
                        } else if cache[b3.start] < cache[a3.end - 1] {
                            let from = UnsafeBufferPointer(cache)
                            let into = UnsafeMutableBufferPointer(
                                rebasing: a[a1Merged.start..<(a1Merged.start + merged1_len + merged2_len)]
                            )
                            octo_merge_into(from, a3, b3, into)
                        } else {
                            for i in 0..<merged1_len {
                                a[a1Merged.start + i] = cache[a3.start + i]
                            }
                            for i in 0..<merged2_len {
                                a[a1Merged.start + merged1_len + i] = cache[b3.start + i]
                            }
                        }
                    }
                    _ = iterator.next_level()
                } else {
                    iterator.begin()
                    while !iterator.finished() {
                        let a_range = iterator.next_range()
                        let b = iterator.next_range()
                        octo_merge_pair(a, a_range, b, cache, cache_size)
                    }
                }
            } else {
                iterator.begin()
                while !iterator.finished() {
                    let a_range = iterator.next_range()
                    let b = iterator.next_range()
                    octo_merge_pair(a, a_range, b, cache, cache_size)
                }
            }
            if !iterator.next_level() {
                break
            }
        }
    }
}


func benchmark_sort(_ array: inout [Int]) {

    octo_sort(&array)

}

func is_non_decreasing(_ a: [Int]) -> Bool {
    guard a.count >= 2 else { return true }
    for i in 1..<a.count {
        if a[i - 1] > a[i] { return false }
    }
    return true
}

func same_multiset(_ a: [Int], _ b: [Int]) -> Bool {
    if a.count != b.count {
        return false
    }

    var left = a
    var right = b
    left.sort()
    right.sort()
    return left == right
}

func check_correctness_case(_ label: String, _ input: [Int]) {
    var input = input
    let original = input

    benchmark_sort(&input)

    if !is_non_decreasing(input) {
        fatalError("correctness case \(label): output is not sorted")
    }

    if !same_multiset(input, original) {
        fatalError("correctness case \(label): elements were lost or added")
    }
}

// Skip cases larger than the algorithm's measured size cap (MAX_POWER). That
// cap exists because larger inputs are impractically slow; forcing them here
// would stall the published measurement script before any table rows print.
func check_correctness_case_within_limit(_ label: String, _ input: [Int]) {
    if input.count > (1 << MAX_POWER) {
        return
    }
    check_correctness_case(label, input)
}

func few_unique_values(_ size: Int, _ unique: Int, _ seed: UInt64) -> [Int] {
    var state = seed
    var result = [Int]()
    result.reserveCapacity(size)
    for _ in 0..<size {
        state ^= state << 13
        state ^= state >> 7
        state ^= state << 17
        result.append(Int(state % UInt64(unique)) + 1)
    }
    return result
}

func run_correctness_checks() {
    check_correctness_case("empty", [])
    check_correctness_case("single", [42])
    check_correctness_case("duplicates", [3, 1, 3, 2, 1, 2])
    check_correctness_case("sorted", [1, 2, 3, 4, 5])
    check_correctness_case("reverse", [5, 4, 3, 2, 1])
    check_correctness_case("all_equal", [7, 7, 7, 7])
    check_correctness_case("skewed_range", [1_000_000, 2, 1_000_001, 1, 999_999])
    // Static-buffer Grail skips the in-buffer build when key collection is sparse
    // (ideal_buffer = false). Exercising that path catches regressions in buffer gating.
    check_correctness_case(
        "few_keys_len16",
        [2, 2, 2, 2, 2, 2, 2, 2, 4, 3, 1, 2, 3, 4, 1, 4]
    )
    // Seed 0 is a fixed point of the xorshift below, so it would degenerate into
    // yet another all-equal case instead of a 4-value mix. Start at 1.
    for seed in 1...32 {
        check_correctness_case(
            "few_keys_len32_seed_\(seed)",
            few_unique_values(32, 4, UInt64(seed))
        )
    }
    // Small-input cutoffs (insertion sort below 32 elements, etc.) hide duplicate-key
    // bugs in the recursive path, so repeat the duplicate cases at the smallest
    // benchmark size, which every algorithm must handle within reasonable time.
    check_correctness_case("all_equal_len256", [Int](repeating: 7, count: 256))
    for seed in 1...4 {
        check_correctness_case(
            "few_keys_len256_seed_\(seed)",
            few_unique_values(256, 4, UInt64(seed))
        )
    }
    // Blit's equal-key second sweep used to copy the whole range into a fixed
    // 512-element swap; lengths above that must still sort without panicking.
    // Respect MAX_POWER so algorithms with a low measured-size cap (slow,
    // sleep) do not hang here for minutes or months.
    check_correctness_case_within_limit("all_equal_len600", [Int](repeating: 7, count: 600))
    for seed in 1...4 {
        check_correctness_case_within_limit(
            "few_keys_len2048_seed_\(seed)",
            few_unique_values(2048, 4, UInt64(seed))
        )
    }
}


func shuffled(_ size: Int, seed: UInt64) -> [Int] {
    guard size > 0 else { return [] }

    var v = Array(1...size)
    var state = seed

    if size > 1 {
        for i in stride(from: size - 1, through: 1, by: -1) {
            state ^= state << 13
            state ^= state >> 7
            state ^= state << 17

            let j = Int(state % UInt64(i + 1))
            v.swapAt(i, j)
        }
    }

    return v
}

func micros(_ d: Duration) -> UInt64 {
    let c = d.components
    let fromSeconds = UInt64(c.seconds) * 1_000_000
    let fromAttos = UInt64(max(0, c.attoseconds / 1_000_000_000_000))
    return fromSeconds + fromAttos
}

func padLeft(_ value: String, _ width: Int) -> String {
    if value.count >= width {
        return value
    }
    return String(repeating: " ", count: width - value.count) + value
}

func formatSeconds(_ micros: UInt64) -> String {
    let whole = micros / 1_000_000
    let frac = micros % 1_000_000
    let fracStr = padLeft(String(frac), 6).replacingOccurrences(of: " ", with: "0")
    return "\(whole).\(fracStr)"
}

func input_array(_ size: Int, seed: UInt64) -> [Int] {
    shuffled(size, seed: seed)
}

/// Peak heap growth during `benchmark_sort`, in bytes (explicit buffers such as swap).
/// Kept in bytes so the parent can average before rounding; converting to KiB here
/// would truncate sub-KiB buffers to 0 in every run and hide them from the average.
func run_once(size: Int, seed: Int) -> (UInt64, Int) {
    var array = input_array(size, seed: UInt64(seed))

    let baseBytes = alloc_track_live()
    alloc_track_reset_peak()

    let start = ContinuousClock.now

    benchmark_sort(&array)

    let elapsed = ContinuousClock.now - start
    let peakBytes = alloc_track_peak()
    let auxBytes = max(0, peakBytes - baseBytes)

    let expected: [Int] = size > 0 ? Array(1...size) : []
    if array != expected {
        fatalError("sort failed with seed \(seed) for size \(size)")
    }

    return (micros(elapsed), auxBytes)
}

func run_child(_ args: [String]) {
    let size = Int(args[2])!
    let seed = Int(args[3])!
    let (elapsedUs, mem) = run_once(size: size, seed: seed)
    print("\(elapsedUs) \(mem)")
}

let args = CommandLine.arguments
if args.count > 1 && args[1] == "--run-once" {
    run_child(args)
} else {
    run_correctness_checks()

    let tableHeader =
        "| \(padLeft("Size", 10)) | " +
        "\(padLeft("Average time (s)", 16)) | " +
        "\(padLeft("Maximum time (s)", 16)) | " +
        "\(padLeft("Average memory (KiB)", 20)) | " +
        "\(padLeft("Maximum memory (KiB)", 20)) |"
    print(tableHeader)
    print("|-----------:|-----------------:|-----------------:|---------------------:|---------------------:|")

    for power in MIN_POWER...MAX_POWER {
        let size = 1 << power

        var totalTime: UInt64 = 0
        var maxTime: UInt64 = 0

        var totalMem = 0
        var maxMem = 0

        for seed in 1...RUNS {
            let process = Process()
            process.executableURL = URL(fileURLWithPath: args[0])
            process.arguments = ["--run-once", "\(size)", "\(seed)"]
            let stdout = Pipe()
            let stderr = Pipe()
            process.standardOutput = stdout
            process.standardError = stderr

            do {
                try process.run()
            } catch {
                fatalError("failed to run benchmark child process: \(error)")
            }
            process.waitUntilExit()

            if process.terminationStatus != 0 {
                let err = String(data: stderr.fileHandleForReading.readDataToEndOfFile(), encoding: .utf8) ?? ""
                fatalError("benchmark child process failed: \(err)")
            }

            let data = stdout.fileHandleForReading.readDataToEndOfFile()
            let stdoutText = String(data: data, encoding: .utf8) ?? ""
            let fields = stdoutText.split(whereSeparator: \.isWhitespace)
            guard fields.count >= 2,
                  let elapsedUs = UInt64(fields[0]),
                  let auxMem = Int(fields[1]) else {
                fatalError("invalid child process output: \(stdoutText)")
            }

            totalTime += elapsedUs
            if elapsedUs > maxTime {
                maxTime = elapsedUs
            }

            totalMem += auxMem
            if auxMem > maxMem {
                maxMem = auxMem
            }
        }

        let avgTime = totalTime / UInt64(RUNS)
        // Memory is summed in bytes and converted to KiB once, after averaging.
        let avgMemKb = totalMem / RUNS / 1024
        let maxMemKb = maxMem / 1024

        let tableRow =
            "| \(padLeft(String(size), 10)) | " +
            "\(padLeft(formatSeconds(avgTime), 16)) | " +
            "\(padLeft(formatSeconds(maxTime), 16)) | " +
            "\(padLeft(String(avgMemKb), 20)) | " +
            "\(padLeft(String(maxMemKb), 20)) |"
        print(tableRow)
    }
}
SWIFT

RUN clang -O2 -fPIC -shared alloc_track.c -o liballoc_track.so -ldl

RUN swiftc -Ounchecked -whole-module-optimization \
    main.swift \
    -o swift-benchmark \
    -L. -lalloc_track \
    -Xlinker -rpath -Xlinker /app

ENV LD_PRELOAD=/app/liballoc_track.so
CMD ["./swift-benchmark"]
"""#
    try dockerfile.write(
        to: workdir.appendingPathComponent("Dockerfile"),
        atomically: true,
        encoding: .utf8
    )

    // Keeping build and run as separate child processes preserves Docker's
    // normal output and the original image tag used by the benchmark skill.
    try runCommand("docker", ["build", "-t", "swift-benchmark", workdir.path])
    try runCommand("docker", ["run", "--rm", "--init", "swift-benchmark"])
} catch {
    fputs("\(error)\n", stderr)
    exit(1)
}