use std::cmp::Ordering;
pub fn sort<T>(a: &mut [T], mut cmp: impl FnMut(&T, &T) -> Ordering) {
let n = a.len();
if n < 2 {
return;
}
let descending = cmp(&a[1], &a[0]).is_lt();
let mut run = 2;
while run < n {
let order = cmp(&a[run], &a[run - 1]);
if if descending {
order.is_ge()
} else {
order.is_lt()
} {
break;
}
run += 1;
}
if descending {
a[..run].reverse();
}
for start in run..n {
let (mut left, mut right) = (0, start);
while left < right {
let mid = left + ((right - left) >> 1);
if cmp(&a[start], &a[mid]).is_lt() {
right = mid;
} else {
left = mid + 1;
}
}
a[left..=start].rotate_right(1);
}
}