// Author Bill Wood
// in-place order N^2
fn main() {
    let mut x = vec!(1,2,2,3,2,5,8,4,9,);
    println!("{:?}", stalin_sort(&mut x));
    let mut x = vec!('a','b','c','b','e','g','d','x');
    println!("{:?}", stalin_sort(&mut x));
    let mut ideologies = vec!(
        "Fully Automated Luxury Space Communism",
        "Socialism",
        "Capitalism",
        "Communism",
    );
    println!("{:?}", stalin_sort(&mut ideologies));
    assert_eq!(vec!(1), stalin_sort(&mut vec!(1)));
    assert_eq!(vec!(1,1), stalin_sort(&mut vec!(1,1)));
    let mut x: Vec<i32> = vec!();
    assert_eq!(x.clone(), stalin_sort(&mut x));
}

fn remove<T: PartialOrd + Default>(v: &mut [T], mut index: usize) -> &mut [T] {
    while index + 1 < v.len() {
        v[index] = std::mem::replace(&mut v[index + 1], Default::default());
        index += 1;
    }
    &mut v[..index]
}

fn stalin_sort<T: PartialOrd + Default>(mut v: &mut [T]) -> &[T] {
    let mut i = 0;
    while i + 1 < v.len() {
        if v[i] > v[i + 1] {
            v = remove(v, i + 1);
        } else {
            i += 1;
        }
    }
    v
}