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

    let mid = items.len() / 2;
    merge_sort(&mut items[..mid]);
    merge_sort(&mut items[mid..]);

    // Both halves are sorted; merge them into a temporary buffer.
    let merged = merge(&items[..mid], &items[mid..]);
    items.clone_from_slice(&merged);
}

/// Merges two sorted slices while preserving the order of equal elements.
fn merge<T: Ord + Clone>(left: &[T], right: &[T]) -> Vec<T> {
    let mut merged = 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] {
            merged.push(left[i].clone());
            i += 1;
        } else {
            merged.push(right[j].clone());
            j += 1;
        }
    }

    merged.extend_from_slice(&left[i..]);
    merged.extend_from_slice(&right[j..]);
    merged
}

fn main() {}

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

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

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

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

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

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