use core::cmp::Ordering;
pub fn sort_by<T>(v: &mut [T], mut cmp: impl FnMut(&T, &T) -> Ordering) {
if v.len() < 2 {
return;
}
let mut idx: Vec<u32> = (0..v.len() as u32).collect();
{
let v: &[T] = v;
sort_idx(&mut idx, &mut |a, b| cmp(&v[a as usize], &v[b as usize]));
}
permute(v, &idx);
}
pub fn sort_by_key<T, K: Ord>(v: &mut [T], mut key: impl FnMut(&T) -> K) {
sort_by(v, |a, b| key(a).cmp(&key(b)));
}
pub fn sort<T: Ord>(v: &mut [T]) {
sort_by(v, T::cmp);
}
#[inline(never)]
fn sort_idx(idx: &mut [u32], cmp: &mut dyn FnMut(u32, u32) -> Ordering) {
idx.sort_by(|a, b| cmp(*a, *b));
}
fn permute<T>(v: &mut [T], idx: &[u32]) {
for i in 0..idx.len() {
let mut j = idx[i] as usize;
while j < i {
j = idx[j] as usize;
}
v.swap(i, j);
}
}
#[cfg(test)]
mod tests {
use super::*;
fn lcg(s: &mut u64) -> u64 {
*s = s.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
*s >> 33
}
#[test]
fn matches_std_stable_sort() {
let mut s = 7u64;
for n in 0..200usize {
for m in [1u64, 3, 1000] {
let v: Vec<(u64, usize)> = (0..n).map(|i| (lcg(&mut s) % m, i)).collect();
let mut a = v.clone();
a.sort_by_key(|x| x.0);
let mut b = v.clone();
sort_by_key(&mut b, |x| x.0);
assert_eq!(a, b, "n {n} m {m}");
let mut c = v.clone();
sort_by(&mut c, |x, y| y.0.cmp(&x.0));
let mut d = v;
d.sort_by(|x, y| y.0.cmp(&x.0));
assert_eq!(c, d);
}
}
let mut w = vec!["b".to_string(), "a".into(), "c".into(), "a".into()];
sort(&mut w);
assert_eq!(w, ["a", "a", "b", "c"]);
}
}