/// Sorts a mutable slice using merge sort.
///
/// This implementation requires `Clone` so merged values can be stored
/// temporarily before being copied back into the slice.
pub fn merge_sort<T: Ord + Clone>(values: &mut [T]) {
    let midpoint = values.len() / 2;

    if midpoint == 0 {
        return;
    }

    merge_sort(&mut values[..midpoint]);
    merge_sort(&mut values[midpoint..]);

    let mut merged = Vec::with_capacity(values.len());
    let (left, right) = values.split_at(midpoint);
    let (mut left_index, mut right_index) = (0, 0);

    while left_index < left.len() && right_index < right.len() {
        if left[left_index] <= right[right_index] {
            merged.push(left[left_index].clone());
            left_index += 1;
        } else {
            merged.push(right[right_index].clone());
            right_index += 1;
        }
    }

    merged.extend_from_slice(&left[left_index..]);
    merged.extend_from_slice(&right[right_index..]);
    values.clone_from_slice(&merged);
}

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

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

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

    #[test]
    fn handles_empty_and_single_element_slices() {
        let mut empty: [i32; 0] = [];
        merge_sort(&mut empty);
        assert_eq!(empty, []);

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