quicksort.rs

fn partition<T: Ord>(a: &mut[T]) -> usize {
    assert!(a.len() >= 2);

    let mut pivot = 0;
    let (mut i, mut j) = (0, a.len());

    loop {
        loop {
            j -= 1;
            if a[j] <= a[pivot] { break; }
        }
        if i >= j { return j; }
        a.swap(i, j);
        if pivot == i { pivot = j; }
        loop {
            i += 1;
            if a[i] >= a[pivot] { break; }
        }
    }
}

fn quicksort<T: Ord>(mut a: &mut[T]) {
    loop {
        if a.len() < 2 { return; }
        let p = partition(a);
        let (left, right) = a.split_at_mut(p + 1);
        quicksort(left);
        a = right;
    }
}

fn main() {
    let mut v = vec![4,2,3,1];
    quicksort(&mut v);
    assert_eq!(v, [1,2,3,4]);

    let mut v = vec![2,4,1,3];
    quicksort(&mut v);
    assert_eq!(v, [1,2,3,4]);
}