use std::cmp::Ordering;

fn merge_sort<T: PartialOrd + Copy>(data: &mut [T]) {
    fn merge<T: PartialOrd + Copy>(left: &mut [T], right: &mut [T], util: &mut [Option<T>]) {
        let mut left_index = 0usize;
        let mut right_index = 0usize;
        let left_len = left.len();
        let right_len = right.len();

        for item in util {
            if (left_index < left_len) &&
            (right_index >= right_len || left[left_index] <= right[right_index]) {
                *item = Some(left[left_index]);
                left_index += 1;
            } else {
                *item = Some(right[right_index]);
                right_index += 1;
            }
        }
    }

    fn tick<T: PartialOrd + Copy>(data: &mut [T], util: &mut [Option<T>]) {
        if data.len() < 2 {
            return
        }

        let middle = data.len() / 2;

        let (data_left, data_right) = data.split_at_mut(middle);
        let (util_left, util_right) = util.split_at_mut(middle);

        tick(data_left, util_left);
        tick(data_right, util_right);

        merge(data_left, data_right, util);

        let util_iter = util.iter().filter_map(|item| *item);

        for (index, item) in util_iter.enumerate() {
            data[index] = item;
        }
    }

    let len = data.len();

    if len < 2 {
        return
    }

    let mut util: Vec<Option<T>> = vec![None; len];

    tick(data, util.as_mut_slice());
}

fn main() {
    fn show_numbers_example(data: &mut [u32]) {
        merge_sort(data);

        println!("{:?}", data);
    }

    show_numbers_example(&mut [38, 27, 43, 3, 9, 82, 10]);
    show_numbers_example(&mut [2, 1]);
    show_numbers_example(&mut [3, 4, 5]);


    fn show_users_example(data: &mut [User]) {
        merge_sort(data);

        println!("{:?}", data);
    }

    show_users_example(&mut [
        User::new(0, "Boris", 21),
        User::new(1, "Sarah", 32),
        User::new(2, "Rose", 12),
        User::new(3, "John", 23)
    ]);
}

#[derive(Clone, Copy, Debug)]
struct User {
    id: u32,
    name: &'static str,
    age: u32
}

impl User {
    fn new(id: u32, name: &'static str, age: u32) -> Self {
        Self {
            id,
            name,
            age
        }
    }
}

impl PartialEq for User {
    fn eq(&self, other: &Self) -> bool {
        self.age == other.age
    }
}

impl PartialOrd for User {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.age.cmp(&other.age))
    }
}