/// Sorts a mutable slice using merge sort.
///
/// This implementation requires `Clone` to build temporary merged buffers.
pub fn merge_sort<T: Ord + Clone>(items: &mut [T]) {
    let mid = items.len() / 2;
    if mid == 0 {
        return;
    }

    merge_sort(&mut items[..mid]);
    merge_sort(&mut items[mid..]);

    let mut merged = Vec::with_capacity(items.len());
    let (left, right) = items.split_at(mid);
    let (mut i, mut j) = (0, 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..]);
    items.clone_from_slice(&merged);
}

fn main() {
    let mut values = [8, 3, 5, 1, 9, 2];
    merge_sort(&mut values);
    println!("{values:?}");
}

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

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

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

    #[test]
    fn handles_empty_and_single_element_slices() {
        let mut empty: Vec<i32> = Vec::new();
        merge_sort(&mut empty);
        assert!(empty.is_empty());

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