Merge Sort
Splits the array in halves recursively, sorts each, then merges them via a buffer.
- Comparisons 0
- Swaps 0
- sorted indices 0
- active range
- compare
- swap
- sorted
Merge buffers
Pseudocode
1 mergeSort(lo, hi)
2 if lo >= hi: return
3 mid = (lo + hi) / 2
4 mergeSort(lo, mid)
5 mergeSort(mid + 1, hi)
6 merge(lo, mid, hi)
7 merge(lo, mid, hi)
8 copy a[lo..mid] to L, a[mid+1..hi] to R
9 while i < |L| and j < |R|
10 if L[i] <= R[j]: a[k++] = L[i++]
11 else: a[k++] = R[j++]
12 copy remaining L into a
13 copy remaining R into a
Step log
How it works, runtime and memory
Merge Sort follows the divide-and-conquer pattern. The divide phase recursively halves the array until only ranges of length 1 remain (sorted by definition). The conquer phase merges pairs of adjacent sorted ranges into a longer sorted range: two pointers walk through the sorted halves L and R, and the smaller of the two pointed elements is written into a buffer. Once one side is empty the rest of the other is appended. The buffer is then copied back into the original array. Because the recursion halves the array log2(n) times and each merge pass costs O(n) total work, the runtime is always O(n log n), regardless of the input: best, average and worst case match. The algorithm needs a linear auxiliary buffer (O(n) extra memory). Equal elements keep their order, so Merge Sort is stable.
Complexity
- Best case
O(n log n) - Average case
O(n log n) - Worst case
O(n log n) - Extra space
O(n)
When to use it
First choice when stability is required, meaning equal elements must keep their relative order, or when the data comes from disk or a network stream. Merge Sort processes the input sequentially and scales to External Sort for data that does not fit into main memory.