Merge and Mergesort

merge

merge combines two already sorted lists into a single sorted list. It generalises insertion to two lists:

let rec merge = function
  | [], ys -> ys
  | xs, [] -> xs
  | x::xs, y::ys ->
      if x <= y then
        x :: merge (xs, y::ys)
      else
        y :: merge (x::xs, ys)

At each step, merge compares the heads of both lists and takes the smaller. It does at most m + n − 1 comparisons, where m and n are the lengths of the input lists. If n = 1, merging degenerates to insertion: it does proportionally more work for less gain.

merge is not tail-recursive, but making it iterative would offer little benefit for the same reasons that apply to append.

Top-down mergesort

Mergesort divides the input into two equal halves (unlike quicksort, which divides by value), sorts each half recursively, and merges the sorted halves:

let rec tmergesort = function
  | [] -> []
  | [x] -> [x]
  | xs ->
      let k = List.length xs / 2 in
      let l = tmergesort (take k xs) in
      let r = tmergesort (drop k xs) in
      merge (l, r)

Complexity

Because take and drop divide the input into equal parts (differing by at most one element), the recurrence is always T(n) = 2_T_(n/2) + n, giving guaranteed O(n log n) in the worst case. Mergesort is asymptotically optimal.

Comparison with quicksort

Algorithm	Average case	Worst case	Typical speed
Quicksort	O(n log n)	O(_n_²)	~0.74 sec
Append-free quicksort	O(n log n)	O(_n_²)	~0.53 sec
Mergesort	O(n log n)	O(n log n)	~1.4 sec

Mergesort is safe (no quadratic worst case) but typically slower than quicksort on random data. The choice of algorithm depends on the application: if worst-case behaviour matters (e.g., real-time systems or adversarial inputs), mergesort is preferable. If average-case performance is the priority and inputs are not expected to be pathologically ordered, quicksort is the better choice.