binary_insertion_sort.rs

fn binary_search<T: PartialOrd>(v: &[T], x: &T) -> usize {
    let mut l = 0;
    let mut r = v.len();
    while l < r {
        let mid = (l + r) / 2;
        if *x < v[mid] {
            r = mid
        } else {
            l = mid + 1
        }
    }
    while l < v.len() - 1 && v[l] == v[l + 1] {
        l += 1
    }
    l
}

fn binary_insertion_sort<T: PartialOrd>(v: &mut [T]) {
    for i in 1..v.len() {
        let j = binary_search(&v[0..i], &v[i]);
        v[j..i + 1].rotate_right(1);
    }
}

fn main() {
    let mut v = [5, 1, 4, 2, 6, 3];
    binary_insertion_sort(&mut v);
    println!("{:?}", v);
}