Merge sort is a comparison-based sorting algorithm that divides the input array into two halves, recursively sorts each half, and then merges the two sorted halves into a single sorted array — achieving Θ(n log n) time in all cases with O(n) auxiliary space.
Merge sort solves sorting by splitting the list in half, sorting each half independently, then merging the two sorted halves — and it does this recursively until each piece has only one element.
Divide, conquer, combine
Merge sort is a divide-and-conquer algorithm. The strategy:
- Divide: split the array into two halves.
- Conquer: recursively sort each half.
- Combine: merge the two sorted halves into one sorted array.
The base case: an array of 0 or 1 elements is already sorted. The recursion goes all the way down to single elements, then merges back up.
def merge_sort(arr):
if len(arr) <= 1: # base case
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # sort left half
right = merge_sort(arr[mid:]) # sort right half
return merge(left, right) # combine
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # stable: <= preserves order
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:]) # append remaining
result.extend(right[j:])
return result
print(merge_sort([5, 2, 8, 1, 9, 3])) # [1, 2, 3, 5, 8, 9]Complexity
| Case | Time | Space |
|---|---|---|
| Best | Θ(n log n) | O(n) |
| Average | Θ(n log n) | O(n) |
| Worst | Θ(n log n) | O(n) |
Merge sort is the only widely-used sort with guaranteed Θ(n log n) in all cases — it never degrades. The O(n) space is for the temporary merge buffer.
Merge sort is always stable
Because the merge step uses <= (left wins on ties), equal elements from the left subarray are always placed before equal elements from the right subarray. This preserves their original relative order — making merge sort stable. This is why Java uses merge sort for object arrays and Python uses Timsort (merge-sort-based) for sorted().
The recurrence: T(n) = 2T(n/2) + Θ(n)
Merge sort splits into two subproblems of size n/2 (the 2T(n/2) term) and does Θ(n) work to merge them. The master theorem Case 2: f(n) = Θ(n) = Θ(nlog₂2) = Θ(n1). Case 2 applies: T(n) = Θ(n log n). Alternatively, by the recursion tree: at each of log₂n levels, Θ(n) merge work is done, giving Θ(n log n) total.
In-place and external merge sort
The standard recursive merge sort uses O(n) auxiliary space. In-place merge sort achieves O(1) auxiliary space but requires O(n log² n) time — a practical disadvantage. External merge sort handles data too large for RAM: split into chunks that fit in memory, sort each chunk, then merge the sorted chunks from disk. This is how databases sort data larger than RAM — n-way external merge uses n sorted runs merged simultaneously.
Bottom-up merge sort
Merge sort can be implemented iteratively (bottom-up) rather than recursively. Start with subarrays of size 1 (all trivially sorted), merge pairs into subarrays of size 2, merge those into size 4, and so on. No recursion, no call stack overhead — uses O(n) space but only O(log n) stack frames in the recursive version anyway.
def merge_sort_iterative(arr):
n = len(arr)
width = 1 # start with size-1 subarrays
while width < n:
for i in range(0, n, 2 * width):
left = arr[i : i + width]
right = arr[i + width : i + 2 * width]
arr[i : i + len(left) + len(right)] = merge(left, right)
width *= 2 # double the subarray size
return arrFormal proof of correctness
Proof by strong induction on n (CLRS §2.3.1). Base case: n=1, array is trivially sorted. Inductive step: assume merge_sort correctly sorts any array of length < n. Then merge_sort(arr[:mid]) correctly sorts the left half and merge_sort(arr[mid:]) correctly sorts the right half (by inductive hypothesis). The merge procedure takes two sorted arrays and produces one sorted array — this is proved separately by the loop invariant: at the start of each iteration, result contains the i+j smallest elements in sorted order. Therefore merge_sort correctly sorts any array of length n.
Cache-oblivious and parallel merge sort
Standard merge sort is cache-aware: the recursion naturally produces small subproblems that fit in cache. Frigo et al. (1999) proved merge sort is asymptotically cache-optimal. Parallel merge sort: with p processors, divide into p chunks, sort each in O((n/p) log(n/p)) time, then merge. A p-way parallel merge achieves O(n log p / p) merge time using a merge tree. Overall parallel complexity: O(n log n / p + n log p) — linear speedup for p ≤ n/log n.
Cormen, T. H. et al. (2022). CLRS (4th ed.), §2.3 — Designing algorithms: merge sort; §4.5 — Master theorem. von Neumann, J. (1945). First published merge sort algorithm in unpublished memorandum. Knuth, D. E. (1998). TAOCP Vol. 3, §5.2.4 — Sorting by merging.