overclocked_sort 0.2.1

use overclocked_sort::overclocked_sort;
use std::time::{Duration, Instant};

#[derive(Clone, Copy)]
struct Lcg {
    state: u64,
}

impl Lcg {
    fn new(seed: u64) -> Self {
        Self { state: seed }
    }

    #[inline(always)]
    fn next_u32(&mut self) -> u32 {
        self.state = self
            .state
            .wrapping_mul(6364136223846793005)
            .wrapping_add(1);
        (self.state >> 32) as u32
    }

    #[inline(always)]
    fn next_i32_inclusive(&mut self, max: i32) -> i32 {
        (self.next_u32() % (max as u32 + 1)) as i32
    }
}

#[derive(Clone)]
struct Case {
    name: &'static str,
    data: Vec<i32>,
}

fn random_dense(n: usize, seed: u64) -> Vec<i32> {
    let mut rng = Lcg::new(seed);
    let mut out = Vec::with_capacity(n);
    for _ in 0..n {
        out.push(rng.next_i32_inclusive(100_000));
    }
    out
}

fn random_sparse(n: usize, seed: u64) -> Vec<i32> {
    let mut rng = Lcg::new(seed);
    let mut out = Vec::with_capacity(n);
    for _ in 0..n {
        out.push(rng.next_u32() as i32);
    }
    out
}

fn descending(n: usize) -> Vec<i32> {
    let mut out = Vec::with_capacity(n);
    for i in 0..n {
        out.push((n - i) as i32);
    }
    out
}

fn ascending(n: usize) -> Vec<i32> {
    (0..n as i32).collect()
}

fn almost_sorted(n: usize, seed: u64) -> Vec<i32> {
    let mut out = ascending(n);
    let swaps = n / 100;
    let mut rng = Lcg::new(seed);
    for _ in 0..swaps {
        let a = (rng.next_u32() as usize) % n;
        let b = (rng.next_u32() as usize) % n;
        out.swap(a, b);
    }
    out
}

fn many_duplicates(n: usize, seed: u64) -> Vec<i32> {
    let mut rng = Lcg::new(seed);
    let mut out = Vec::with_capacity(n);
    for _ in 0..n {
        out.push(rng.next_i32_inclusive(7));
    }
    out
}

fn organ_pipe(n: usize) -> Vec<i32> {
    let mut out = Vec::with_capacity(n);
    let mid = n / 2;
    for i in 0..mid {
        out.push(i as i32);
    }
    for i in (0..(n - mid)).rev() {
        out.push(i as i32);
    }
    out
}

fn sawtooth(n: usize, period: i32) -> Vec<i32> {
    let mut out = Vec::with_capacity(n);
    for i in 0..n {
        out.push((i as i32) % period);
    }
    out
}

fn all_equal(n: usize, value: i32) -> Vec<i32> {
    vec![value; n]
}

fn median_duration(v: &mut [Duration]) -> Duration {
    v.sort_unstable();
    v[v.len() / 2]
}

fn is_sorted_non_decreasing(data: &[i32]) -> bool {
    data.windows(2).all(|w| w[0] <= w[1])
}

fn run_case(case: &Case, repeats: usize) {
    let mut overclocked_runs = Vec::with_capacity(repeats);
    let mut std_runs = Vec::with_capacity(repeats);

    for r in 0..repeats {
        let mut a = case.data.clone();
        let mut b = case.data.clone();

        if r % 2 == 0 {
            let t0 = Instant::now();
            overclocked_sort(&mut a);
            overclocked_runs.push(t0.elapsed());

            let t1 = Instant::now();
            b.sort_unstable();
            std_runs.push(t1.elapsed());
        } else {
            let t0 = Instant::now();
            b.sort_unstable();
            std_runs.push(t0.elapsed());

            let t1 = Instant::now();
            overclocked_sort(&mut a);
            overclocked_runs.push(t1.elapsed());
        }

        assert!(is_sorted_non_decreasing(&a), "overclocked_sort output is not sorted");
        assert!(is_sorted_non_decreasing(&b), "std::sort_unstable output is not sorted");
        assert_eq!(a, b, "result mismatch with std::sort_unstable");
    }

    let oc_med = median_duration(&mut overclocked_runs);
    let std_med = median_duration(&mut std_runs);
    let ratio = std_med.as_secs_f64() / oc_med.as_secs_f64();

    println!(
        "| {:<24} | {:>9} | {:>10.3} ms | {:>10.3} ms | {:>7.3}x |",
        case.name,
        case.data.len(),
        oc_med.as_secs_f64() * 1000.0,
        std_med.as_secs_f64() * 1000.0,
        ratio,
    );
}

fn main() {
    let n = 2_000_000;
    let repeats = 5;

    let cases = vec![
        Case {
            name: "random_dense",
            data: random_dense(n, 101),
        },
        Case {
            name: "random_sparse",
            data: random_sparse(n, 202),
        },
        Case {
            name: "already_sorted",
            data: ascending(n),
        },
        Case {
            name: "reverse_sorted",
            data: descending(n),
        },
        Case {
            name: "almost_sorted_1pct",
            data: almost_sorted(n, 303),
        },
        Case {
            name: "many_duplicates",
            data: many_duplicates(n, 404),
        },
        Case {
            name: "organ_pipe",
            data: organ_pipe(n),
        },
        Case {
            name: "sawtooth_1024",
            data: sawtooth(n, 1024),
        },
        Case {
            name: "all_equal",
            data: all_equal(n, 42),
        },
        Case {
            name: "tiny_1",
            data: vec![1],
        },
        Case {
            name: "tiny_empty",
            data: Vec::new(),
        },
    ];

    println!("=== Overclocked Sort vs std::sort_unstable ===");
    println!("n = {}, repeats = {} (median)\n", n, repeats);
    println!("| Case                     |         N | Overclocked |        std |   Speed |",);
    println!("|--------------------------|-----------|-------------|------------|---------|");

    for case in &cases {
        run_case(case, repeats);
    }
}