fn main() {
    let mut array = vec![true, false, false, false];//43, 97, 45, 54, 91, 16, 76, 18, 88, 89, 87, 5, 66, 29, 61, 8, 85, 30, 81, 89, 89, 43, 67, 7, 50, 23, 48, 83, 88, 36, 80, 76, 85, 4, 83, 30, 68, 66, 65, 5, 18, 6, 88, 1, 17, 4, 23, 40, 70, 41];
    sort(&mut array[..]);
    println!("{:?}", array);
}

fn sort3<T : PartialOrd>(array : &mut [T]) {
    let n = array.len();
    assert!(n <= 3);

    if n <= 1 {
        return;
    }

    if array[0] > array[1] {
        array.swap(0, 1);
    }

    if n == 2 {
        return;
    }

    if array[1] > array[2] {
        array.swap(1, 2);
    }

    if array[0] > array[1] {
        array.swap(0, 1);
    }
}

fn merge<T : PartialOrd>(left : &mut [T], right : &mut [T]) {
    let left_len = left.len();
    let right_len = right.len();
    let mut vec = Vec::with_capacity(left_len + right_len);
    let mut i = 0;
    let mut j = 0;

    while i < left_len && j < right_len {
        if left[i] < right[j] {
            let next = std::mem::replace(&mut left[i], unsafe { std::mem::uninitialized() });
            vec.push(next);
            i += 1;
        } else {
            let next = std::mem::replace(&mut right[j], unsafe { std::mem::uninitialized() });
            vec.push(next);
            j += 1;
        }
    }

    while i < left_len {
        let next = std::mem::replace(&mut left[i], unsafe { std::mem::uninitialized() });
        vec.push(next);
        i += 1;
    }

    while j < right_len {
        let next = std::mem::replace(&mut right[j], unsafe { std::mem::uninitialized() });
        vec.push(next);
        j += 1;
    }

    let mut k = 0;
    for item in vec {
        if k < left_len {
            unsafe { std::ptr::write(&mut left[k], item); }
        } else {
            unsafe { std::ptr::write(&mut right[k - left_len], item); }
        }

        k += 1;
    }
}

fn sort<T : PartialOrd>(array : &mut [T]) {
    let n = array.len();
    if n <= 3 {
        sort3(array);
    } else {
        let (left, right) = array.split_at_mut(n / 2);
        sort(left);
        sort(right);
        merge(left, right);
    }
}