075: Merge Sort

Difficulty: Intermediate Category: Algorithms Concept: Divide-and-conquer sorting: split, sort halves, merge Key Insight: Merge sort is naturally recursive and functional — splitting and merging lists is elegant in both languages.

// 075: Merge Sort

// Approach 1: Classic recursive merge sort
fn merge(l1: &[i32], l2: &[i32]) -> Vec<i32> {
    let mut result = Vec::with_capacity(l1.len() + l2.len());
    let (mut i, mut j) = (0, 0);
    while i < l1.len() && j < l2.len() {
        if l1[i] <= l2[j] {
            result.push(l1[i]);
            i += 1;
        } else {
            result.push(l2[j]);
            j += 1;
        }
    }
    result.extend_from_slice(&l1[i..]);
    result.extend_from_slice(&l2[j..]);
    result
}

fn merge_sort(v: &[i32]) -> Vec<i32> {
    if v.len() <= 1 {
        return v.to_vec();
    }
    let mid = v.len() / 2;
    let left = merge_sort(&v[..mid]);
    let right = merge_sort(&v[mid..]);
    merge(&left, &right)
}

// Approach 2: Generic with comparator
fn merge_sort_by<T: Clone, F>(v: &[T], cmp: &F) -> Vec<T>
where
    F: Fn(&T, &T) -> std::cmp::Ordering,
{
    if v.len() <= 1 { return v.to_vec(); }
    let mid = v.len() / 2;
    let left = merge_sort_by(&v[..mid], cmp);
    let right = merge_sort_by(&v[mid..], cmp);
    let mut result = Vec::with_capacity(v.len());
    let (mut i, mut j) = (0, 0);
    while i < left.len() && j < right.len() {
        if cmp(&left[i], &right[j]) != std::cmp::Ordering::Greater {
            result.push(left[i].clone()); i += 1;
        } else {
            result.push(right[j].clone()); j += 1;
        }
    }
    result.extend_from_slice(&left[i..]);
    result.extend_from_slice(&right[j..]);
    result
}

// Approach 3: Functional style with iterators
fn merge_sort_fn(v: &[i32]) -> Vec<i32> {
    if v.len() <= 1 { return v.to_vec(); }
    let mid = v.len() / 2;
    merge(&merge_sort_fn(&v[..mid]), &merge_sort_fn(&v[mid..]))
}

fn main() {
    let v = vec![5, 3, 8, 1, 9, 2, 7];
    println!("merge_sort = {:?}", merge_sort(&v));
    println!("desc = {:?}", merge_sort_by(&v, &|a: &i32, b: &i32| b.cmp(a)));
}

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

    #[test]
    fn test_merge_sort() {
        assert_eq!(merge_sort(&[5, 3, 8, 1, 9, 2, 7]), vec![1, 2, 3, 5, 7, 8, 9]);
        assert_eq!(merge_sort(&[]), Vec::<i32>::new());
        assert_eq!(merge_sort(&[1]), vec![1]);
        assert_eq!(merge_sort(&[2, 1]), vec![1, 2]);
    }

    #[test]
    fn test_merge_sort_by() {
        let v = vec![5, 3, 8, 1];
        assert_eq!(merge_sort_by(&v, &|a: &i32, b: &i32| a.cmp(b)), vec![1, 3, 5, 8]);
        assert_eq!(merge_sort_by(&v, &|a: &i32, b: &i32| b.cmp(a)), vec![8, 5, 3, 1]);
    }

    #[test]
    fn test_merge_sort_fn() {
        assert_eq!(merge_sort_fn(&[5, 3, 8, 1, 9, 2, 7]), vec![1, 2, 3, 5, 7, 8, 9]);
    }
}

(* 075: Merge Sort *)

(* Approach 1: Classic recursive merge sort *)
let rec merge l1 l2 =
  match l1, l2 with
  | [], l | l, [] -> l
  | x :: xs, y :: ys ->
    if x <= y then x :: merge xs (y :: ys)
    else y :: merge (x :: xs) ys

let rec split = function
  | [] -> ([], [])
  | [x] -> ([x], [])
  | x :: y :: rest ->
    let (l, r) = split rest in
    (x :: l, y :: r)

let rec merge_sort = function
  | [] -> []
  | [x] -> [x]
  | lst ->
    let (l, r) = split lst in
    merge (merge_sort l) (merge_sort r)

(* Approach 2: Generic merge sort with comparator *)
let rec merge_by cmp l1 l2 =
  match l1, l2 with
  | [], l | l, [] -> l
  | x :: xs, y :: ys ->
    if cmp x y <= 0 then x :: merge_by cmp xs (y :: ys)
    else y :: merge_by cmp (x :: xs) ys

let rec merge_sort_by cmp = function
  | [] -> []
  | [x] -> [x]
  | lst ->
    let (l, r) = split lst in
    merge_by cmp (merge_sort_by cmp l) (merge_sort_by cmp r)

(* Approach 3: Bottom-up style using fold *)
let merge_sort_fold lst =
  let singletons = List.map (fun x -> [x]) lst in
  let rec reduce = function
    | [] -> []
    | [x] -> x
    | pairs ->
      let rec pair_merge = function
        | [] -> []
        | [x] -> [x]
        | x :: y :: rest -> merge x y :: pair_merge rest
      in
      reduce (pair_merge pairs)
  in
  reduce singletons

(* Tests *)
let () =
  assert (merge_sort [5; 3; 8; 1; 9; 2; 7] = [1; 2; 3; 5; 7; 8; 9]);
  assert (merge_sort [] = []);
  assert (merge_sort [1] = [1]);
  assert (merge_sort [2; 1] = [1; 2]);
  assert (merge_sort_by compare [5; 3; 8; 1] = [1; 3; 5; 8]);
  assert (merge_sort_by (fun a b -> compare b a) [5; 3; 8; 1] = [8; 5; 3; 1]);
  assert (merge_sort_fold [5; 3; 8; 1; 9; 2; 7] = [1; 2; 3; 5; 7; 8; 9]);
  Printf.printf "✓ All tests passed\n"

📊 Detailed Comparison

Core Insight

Merge sort: split into halves, recursively sort each half, merge sorted halves. O(n log n) guaranteed. The functional version is particularly elegant because merging sorted lists is a natural recursive operation.

OCaml Approach

Pattern match on list to split
Recursive merge of two sorted lists
No mutation — creates new lists at each step

Rust Approach

Split slice at midpoint
Recursive sort on sub-slices
Merge into new Vec — or use `sort()` (introsort)

Comparison Table

Feature	OCaml	Rust
Split	Pattern match / `List.nth`	`split_at(mid)`
Merge	Recursive cons	Push to Vec
In-place	No (functional)	Possible but complex
Built-in	`List.sort`	`.sort()` (introsort)