use std::cmp::Ordering;
fn cmp_at<T>(items: &[T], a: usize, b: usize, cmp: &impl Fn(&T, &T) -> Ordering) -> Ordering {
match (items.get(a), items.get(b)) {
(Some(x), Some(y)) => cmp(x, y),
_ => Ordering::Equal,
}
}
const QSORT_CUTOFF: usize = 8;
pub(crate) fn msvc_qsort<T>(items: &mut [T], cmp: impl Fn(&T, &T) -> Ordering) {
use Ordering::{Equal, Greater};
let Some(last) = items.len().checked_sub(1) else {
return;
};
let mut stack = vec![(0usize, last)];
while let Some((lo, mut hi)) = stack.pop() {
if hi <= lo {
continue;
}
let size = hi - lo + 1;
if size <= QSORT_CUTOFF {
while hi > lo {
let mut max = lo;
for p in lo + 1..=hi {
if cmp_at(items, p, max, &cmp) == Greater {
max = p;
}
}
items.swap(max, hi);
hi -= 1;
}
continue;
}
let mut mid = lo + size / 2;
if cmp_at(items, lo, mid, &cmp) == Greater {
items.swap(lo, mid);
}
if cmp_at(items, lo, hi, &cmp) == Greater {
items.swap(lo, hi);
}
if cmp_at(items, mid, hi, &cmp) == Greater {
items.swap(mid, hi);
}
let mut loguy = lo;
let mut higuy = hi;
loop {
if mid > loguy {
loop {
loguy += 1;
if !(loguy < mid && cmp_at(items, loguy, mid, &cmp) != Greater) {
break;
}
}
}
if mid <= loguy {
loop {
loguy += 1;
if !(loguy <= hi && cmp_at(items, loguy, mid, &cmp) != Greater) {
break;
}
}
}
loop {
higuy = higuy.saturating_sub(1);
if !(higuy > mid && cmp_at(items, higuy, mid, &cmp) == Greater) {
break;
}
}
if higuy < loguy {
break;
}
items.swap(loguy, higuy);
if mid == higuy {
mid = loguy;
}
}
higuy += 1;
if mid < higuy {
loop {
higuy = higuy.saturating_sub(1);
if !(higuy > mid && cmp_at(items, higuy, mid, &cmp) == Equal) {
break;
}
}
}
if mid >= higuy {
loop {
higuy = higuy.saturating_sub(1);
if !(higuy > lo && cmp_at(items, higuy, mid, &cmp) == Equal) {
break;
}
}
}
let left = (lo < higuy).then_some((lo, higuy));
let right = (loguy < hi).then_some((loguy, hi));
let len = |r: &(usize, usize)| r.1 - r.0;
let (first, second) = match (left, right) {
(Some(l), Some(r)) if len(&l) < len(&r) => (Some(r), Some(l)),
other => other,
};
stack.extend(first);
stack.extend(second);
}
}
#[cfg(test)]
mod tests {
use super::*;
fn items(keys: &[u16]) -> Vec<(u16, i32)> {
keys.iter()
.enumerate()
.map(|(i, &k)| (k, i32::try_from(i).expect("small")))
.collect()
}
fn order(keys: &[u16]) -> Vec<i32> {
let mut v = items(keys);
msvc_qsort(&mut v, |a, b| a.0.cmp(&b.0));
let sorted: Vec<u16> = v.iter().map(|x| x.0).collect();
assert!(sorted.is_sorted(), "not sorted: {sorted:?}");
v.iter().map(|x| x.1).collect()
}
#[test]
fn msvc_qsort_matches_reference_orders() {
assert_eq!(order(&[]), Vec::<i32>::new());
assert_eq!(order(&[5]), vec![0]);
assert_eq!(order(&[1, 1]), vec![1, 0]);
assert_eq!(order(&[1, 2]), vec![0, 1]);
assert_eq!(order(&[2, 1]), vec![1, 0]);
assert_eq!(order(&[1, 1, 1]), vec![1, 2, 0]);
assert_eq!(order(&[3; 8]), vec![1, 2, 3, 4, 5, 6, 7, 0]);
assert_eq!(
order(&[2, 1, 2, 1, 2, 1, 2, 1]),
vec![1, 5, 3, 7, 4, 6, 2, 0]
);
assert_eq!(order(&[4; 9]), (0..9).collect::<Vec<i32>>());
assert_eq!(
order(&[8, 7, 6, 5, 4, 3, 2, 1, 0]),
vec![8, 7, 6, 5, 4, 3, 2, 1, 0]
);
assert_eq!(
order(&[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]),
vec![11, 1, 7, 3, 5, 9, 2, 8, 6, 4, 10, 0]
);
assert_eq!(
order(&[0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0]),
vec![0, 8, 12, 4, 3, 5, 2, 7, 1, 9, 10, 11, 6]
);
}
#[test]
fn msvc_qsort_all_equal_terminates() {
let mut v = items(&[7; 1000]);
msvc_qsort(&mut v, |_, _| Ordering::Equal);
let mut ids: Vec<i32> = v.iter().map(|x| x.1).collect();
ids.sort_unstable();
assert_eq!(ids, (0..1000).collect::<Vec<i32>>());
}
#[test]
fn msvc_qsort_sorts_larger_inputs() {
let mut x = 12345u32;
let random: Vec<u16> = (0..500)
.map(|_| {
x = x.wrapping_mul(1_103_515_245).wrapping_add(12345);
u16::try_from((x >> 16) % 37).expect("small")
})
.collect();
let sorted: Vec<u16> = (0..300).collect();
let reversed: Vec<u16> = (0..300).rev().collect();
for keys in [random, sorted, reversed] {
let got = order(&keys);
let mut seen = got.clone();
seen.sort_unstable();
let n = i32::try_from(keys.len()).expect("small");
assert_eq!(seen, (0..n).collect::<Vec<i32>>());
}
}
}