Merge Sort Algorithm (WIP)

Merge sort is a divide-and-conquer algorithm that splits an array into halves, recursively sorts each half, and then merges the sorted halves to produce the final sorted array.

  1. Split the array into two halves.
  2. Recursively sort each half.
  3. Merge the two sorted halves into a single sorted array.
fn merge_sort<T: Ord + Clone>(arr: &mut [T]) {
    let mid = arr.len() / 2;
    if mid == 0 {
        return;
    }

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

    let mut ret = arr.to_vec();

    merge(&arr[..mid], &arr[mid..], &mut ret[..]);

    arr.copy_from_slice(&ret);
}

fn merge<T: Ord + Clone>(left: &[T], right: &[T], ret: &mut [T]) {
    let mut left_iter = left.iter();
    let mut right_iter = right.iter();
    let mut left_peek = left_iter.next();
    let mut right_peek = right_iter.next();
    let mut i = 0;

    while let (Some(left_val), Some(right_val)) = (left_peek, right_peek) {
        if left_val <= right_val {
            ret[i] = left_val.clone();
            left_peek = left_iter.next();
        } else {
            ret[i] = right_val.clone();
            right_peek = right_iter.next();
        }
        i += 1;
    }

    while let Some(left_val) = left_peek {
        ret[i] = left_val.clone();
        left_peek = left_iter.next();
        i += 1;
    }

    while let Some(right_val) = right_peek {
        ret[i] = right_val.clone();
        right_peek = right_iter.next();
        i += 1;
    }
}

fn main() {
    let mut arr = vec![38, 27, 43, 3, 9, 82, 10];
    println!("Original array: {:?}", arr);
    merge_sort(&mut arr);
    println!("Sorted array: {:?}", arr);
}
  • merge_sort function: Recursively splits the array into halves and sorts each half.
  • merge function: Merges two sorted slices into a single sorted slice.

This implementation ensures that the array is sorted in-place using the merge sort algorithm.