// Author Bill Wood
// in-place, order N
fn main() {
    let mut x = vec!(1,2,2,3,2,1,5,8,4,9,);
    println!("{:?}", stalin_sort(&mut x));
    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 stalin_sort<T: PartialOrd + std::fmt::Debug>(v: &mut [T]) -> &[T] {
    let mut i = 1;
    let mut len = v.len();
    while i < len {
        v.swap(i, i + v.len() - len);
        if v[i] >= v[i - 1] {
            i += 1;
        } else {
            len -= 1;
            //println!("{:?}", &v[..len]);
        }
    }
    &v[..len]
}