dual_quick_sort.rs

fn partition<T: PartialOrd>(v: &mut [T]) -> (usize, usize) {
    let len = v.len();
    let end = len - 1;
    if v[0] > v[end] {
        v.swap(0, end)
    }
    let mut j = 1;
    let mut g = end - 1;
    let mut k = 1;
    while k <= g {
        if v[k] < v[0] {
            v.swap(k, j);
            j += 1;
        } else if v[k] >= v[end] {
            while v[g] > v[end] && k < g {
                g -= 1;
            }
            v.swap(k, g);
            g -= 1;
            if v[k] < v[0] {
                v.swap(k, j);
                j += 1;
            }
        }
        k += 1;
    }
    j -= 1;
    g += 1;
    v.swap(0, j);
    v.swap(end, g);
    (j, g)
}

fn dual_quick_sort<T: PartialOrd>(v: &mut [T]) {
    if v.len() < 2 {
        return;
    }
    let (l, r) = partition(v);
    dual_quick_sort(&mut v[0..l]);
    dual_quick_sort(&mut v[l + 1..r]);
    dual_quick_sort(&mut v[r + 1..]);
}

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