1. Merge Sort

Merge sort is the archetypal divide-and-conquer sorting algorithm. Given an array of \(n\) elements it recursively splits the array into two halves, sorts each half independently, and then merges the two sorted halves into a single sorted sequence in \(O(n)\) time. The total cost satisfies a recurrence that evaluates to the information-theoretically optimal \(O(n \log n)\). Cormen et al. ¹ introduce merge sort as the first major algorithm studied in CLRS precisely because its recurrence, proof of correctness, and stability make it the cleanest illustration of the divide-and-conquer paradigm.

1.1 Problem Statement

Given a sequence \(A = \langle a_0, a_1, \ldots, a_{n-1} \rangle\) drawn from a totally ordered set, produce a permutation \(A'\) such that \(a'_0 \leq a'_1 \leq \cdots \leq a'_{n-1}\).

1.2 Mathematical Foundation

1.2.1 Recurrence

Splitting an array of size \(n\) into two halves and merging the sorted results gives the recurrence:

By the Master Theorem with \(a = 2\), \(b = 2\), \(k = 1\) (so \(a = b^k\), case 2):

This holds in the best, average, and worst case — merge sort has no bad inputs.

1.2.2 Comparison Lower Bound

Any comparison-based sorting algorithm requires \(\Omega(n \log n)\) comparisons in the worst case. The argument uses a decision-tree model: a binary tree whose leaves represent the \(n!\) possible input permutations must have height \(\geq \log_2(n!) = \Omega(n \log n)\) by Stirling's formula. Merge sort achieves this bound, making it asymptotically optimal among comparison-based sorts ¹.

1.3 The Algorithm

1.3.1 Top-Down (Recursive)

MERGESORT(A, p, r):
  if p < r:
    q = ⌊(p + r) / 2⌋
    MERGESORT(A, p, q)
    MERGESORT(A, q + 1, r)
    MERGE(A, p, q, r)

MERGE(A, p, q, r):
  // copy left and right halves into temporary arrays L, R
  n₁ = q - p + 1;  n₂ = r - q
  for i = 0 to n₁ - 1: L[i] = A[p + i]
  for j = 0 to n₂ - 1: R[j] = A[q + 1 + j]
  i = 0;  j = 0;  k = p
  while i < n₁ and j < n₂:
    if L[i] ≤ R[j]:  A[k] = L[i];  i++
    else:             A[k] = R[j];  j++
    k++
  // copy any remaining elements
  while i < n₁: A[k++] = L[i++]
  while j < n₂: A[k++] = R[j++]

Initial call: MERGESORT(A, 0, n - 1).

1.3.2 Correctness: Loop Invariant in MERGE

At the start of each iteration of the outer while loop in MERGE, with cursor \(k\):

Sub-array \(A[p..k-1]\) contains the \(k - p\) smallest elements of \(L \cup R\), in sorted order.

Initialisation: \(k = p\), the sub-array is empty — trivially holds.
Maintenance: each step places min(L[i], R[j]) at \(A[k]\), which is the \((k - p + 1)\)-th smallest element of \(L \cup R\).
Termination: when one pointer is exhausted the remaining elements are already in sorted order and are copied directly.

1.3.3 Bottom-Up (Iterative) Variant

The recursion can be eliminated by merging sub-arrays of increasing size \(w = 1, 2, 4, \ldots\) in a single left-to-right pass per doubling. This avoids function call overhead and is preferred in production implementations.

1.4 Complexity

The \(O(n)\) auxiliary space is used for the temporary arrays in MERGE. In-place merge sort variants exist but either sacrifice the \(O(n \log n)\) time or require complex pointer manipulation ¹.

1.5 Properties

1.5.1 Stability

Merge sort is stable: equal elements appear in the original relative order in the sorted output. This follows directly from the ≤ comparison in MERGE: when L[i] = R[j], the left element is chosen first, preserving relative order. Stability is critical when sorting compound records (e.g. sorting first by last name, then by first name using two stable passes is equivalent to a single two-key sort).

1.5.2 External Sorting

Merge sort is the basis of external sorting — sorting data sets larger than main memory. The array is divided into runs small enough to fit in RAM, each run is sorted in memory, and runs are then merged from disk. The number of passes over the data is \(O(\log_k n)\) where \(k\) is the number of simultaneous merge streams, and is determined by available memory ²¹.

1.6 Comparison with Other Sorts

Quick sort is typically faster in practice due to better cache performance and smaller constants, but its \(O(n^2)\) worst case motivates the use of merge sort or heap sort when worst-case guarantees are required ³¹.

1.7 Interactive Demo

The canvas below animates merge sort on a 16-element array. The array is shown at each step; colours indicate sub-array boundaries and the current merge operation.