/// Sorts `items` in ascending order using stable merge sort.
pub fn merge_sort<T: Ord + Clone>(items: &mut [T]) {
    let len = items.len();

    if len <= 1 {
        return;
    }

    let mid = len / 2;
    let mut left = items[..mid].to_vec();
    let mut right = items[mid..].to_vec();

    merge_sort(&mut left);
    merge_sort(&mut right);

    merge(&left, &right, items);
}

/// Merges two sorted slices into `out`.
fn merge<T: Ord + Clone>(left: &[T], right: &[T], out: &mut [T]) {
    let mut i = 0;
    let mut j = 0;
    let mut k = 0;

    while i < left.len() && j < right.len() {
        // Prefer the left item on equality to keep the sort stable.
        if left[i] <= right[j] {
            out[k] = left[i].clone();
            i += 1;
        } else {
            out[k] = right[j].clone();
            j += 1;
        }
        k += 1;
    }

    while i < left.len() {
        out[k] = left[i].clone();
        i += 1;
        k += 1;
    }

    while j < right.len() {
        out[k] = right[j].clone();
        j += 1;
        k += 1;
    }
}

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

    #[test]
    fn sorts_integers() {
        let mut values = vec![8, 3, 5, 4, 7, 6, 1, 2];
        merge_sort(&mut values);
        assert_eq!(values, vec![1, 2, 3, 4, 5, 6, 7, 8]);
    }

    #[test]
    fn handles_empty_and_single_item_slices() {
        let mut empty: Vec<i32> = vec![];
        merge_sort(&mut empty);
        assert_eq!(empty, Vec::<i32>::new());

        let mut one = vec![42];
        merge_sort(&mut one);
        assert_eq!(one, vec![42]);
    }

    #[test]
    fn sorts_with_duplicates() {
        let mut values = vec![4, 1, 3, 4, 2, 1, 5];
        merge_sort(&mut values);
        assert_eq!(values, vec![1, 1, 2, 3, 4, 4, 5]);
    }

    #[test]
    fn sorts_strings() {
        let mut words = vec!["pear", "apple", "orange", "banana"];
        merge_sort(&mut words);
        assert_eq!(words, vec!["apple", "banana", "orange", "pear"]);
    }
}