/// Sorts a slice in-place-ish with mergesort.
/// Time Complexity:  O(n * log(n))
/// Space Complexity: O(n)
///
/// ```
/// use merge_sort::merge_sort;
///
/// let mut example = [1,4,2,5,3];
///
/// merge_sort(&mut example);
/// assert_eq!(example, [1,2,3,4,5]);
/// ```
pub fn merge_sort<T: Copy + PartialOrd>(input: &mut [T]) {
    let length = input.len();

    // Base case
    if length < 2 {
        return;
    }

    let mut merged = Vec::with_capacity(length);

    // New code block to enforce "left" and "right" lifetimes, which otherwise
    // would continue ownership of "merged", preventing moving the values back
    // to input.
    {
        // Divide the input in half and sort each half recursively before re-merging.
        let (left, right) = input.split_at_mut(length / 2);
        merge_sort(left);
        merge_sort(right);

        let mut left_iter = left.iter().peekable();
        let mut right_iter = right.iter().peekable();

        // Iterate through left and right sides finding the next lowest value
        while let (Some(&l), Some(&r)) = (left_iter.peek(), right_iter.peek()) {
            if *r < *l {
                merged.push(*(right_iter.next().unwrap()));
            } else {
                merged.push(*(left_iter.next().unwrap()));
            }
        }

        // If any values remain in left, push them onto merged
        for l in left_iter {
            merged.push(*l);
        }

        // If any values remain in right, push them onto merged
        for r in right_iter {
            merged.push(*r);
        }
    }

    // Copy the values from merged back over to the input
    assert!(
        merged.len() == length,
        "All elements from the input should be included in the sorted output"
    );
    for n in 0..length {
        input[n] = merged[n];
    }
}

#[cfg(test)]
mod tests {
    use merge_sort;

    #[test]
    fn it_works() {
        let mut example = [4, 3];
        merge_sort(&mut example);
        assert_eq!(example, [3, 4]);
    }

    #[test]
    fn already_sorted() {
        let mut example = [2, 3, 4, 5];
        merge_sort(&mut example);
        assert_eq!(example, [2, 3, 4, 5]);
    }

    #[test]
    fn base_case() {
        let mut example = [3];
        merge_sort(&mut example);
        assert_eq!(example, [3]);
    }

    #[test]
    fn totally_backwards() {
        let mut example = [100, 90, 50, 14, 9, 7, 3];
        merge_sort(&mut example);
        assert_eq!(example, [3, 7, 9, 14, 50, 90, 100]);
    }
}