fn quick_sort<T: Ord + Copy>(array: &mut[T]) {
    if array.len() < 2 {
        return;
    }

    let pivot = array[array.len() / 2];
    let mut i = 0;
    let mut j = array.len() - 1;

    loop {
        while pivot > array[i] {
            i += 1;
        }
        while pivot < array[j] {
            j -= 1;
        }
        if i >= j {
            break;
        }
        array.swap(i, j);
        i += 1;
        j -= 1;
    }
    if i > 0 {
        quick_sort(&mut array[.. i]);
    }
    if j < array.len() - 1 {
        quick_sort(&mut array[j + 1 ..]);
    }
}

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