pub fn merge_sort<T: Ord + Clone>(items: &[T]) -> Vec<T> {
    if items.len() <= 1 {
        return items.to_vec();
    }

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

    merge(&left, &right)
}

// Merge two already-sorted slices into one sorted vector.
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() {
    let values = vec![5, 2, 9, 1, 5, 6];
    println!("{:?}", merge_sort(&values));
}

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

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

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

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