Merge Sort

Overview

Classic merge sort parameterized by a comparison function. Sort anything ascending, descending, or by custom criteria. Both split and merge are tail-recursive to handle large inputs without stack overflow.

The Algorithm

Split

Divide a list into two roughly equal halves (tail-recursive):

let split lst =
  let rec aux left right = function
    | [] -> (List.rev left, List.rev right)
    | [x] -> (List.rev (x :: left), List.rev right)
    | x :: y :: rest -> aux (x :: left) (y :: right) rest
  in aux [] [] lst

Merge

Merge two sorted lists using an accumulator for tail recursion:

let merge cmp l1 l2 =
  let rec aux acc l1 l2 = match l1, l2 with
    | [], l | l, [] -> List.rev_append acc l
    | h1 :: t1, h2 :: t2 ->
      if cmp h1 h2 <= 0 then aux (h1 :: acc) t1 l2
      else aux (h2 :: acc) l1 t2
  in aux [] l1 l2

Sort

let rec mergesort cmp = function
  | ([] | [_]) as l -> l
  | lst ->
    let (left, right) = split lst in
    merge cmp (mergesort cmp left) (mergesort cmp right)

Flexible Comparison

Pass any comparison function to sort in different orders:

mergesort compare data                       (* ascending *)
mergesort (fun a b -> compare b a) data     (* descending *)
mergesort String.compare words                (* strings *)

Output

Original:    [38; 27; 43; 3; 9; 82; 10]
Sorted asc:  [3; 9; 10; 27; 38; 43; 82]
Sorted desc: [82; 43; 38; 27; 10; 9; 3]
Words sorted: [apple; banana; cherry; date]