Merge Sort: Divide, Merge and Guarantees
Split the array until single values remain, then merge sorted runs pairwise until one sorted array is left.
Divide, Then Merge
Merge sort is the clearest example of divide and conquer, and the whole algorithm is three moves:
- Divide split the array at the midpoint. This is positional, so no input can unbalance it.
- Conquer sort each half by the same method, recursing until a piece has length 1 and is sorted by definition.
- Merge walk both sorted halves with one index each, repeatedly taking the smaller of the two front values.
The recursion bottoms out at length 1, which is sorted by definition — no comparison needed. All the actual work happens on the way back up, in the merge.
Why the merge is correct is worth stating precisely: because both halves are already sorted, the smaller of the two front values is the smallest value not yet placed anywhere. So each comparison commits one element permanently, and merging two runs of total length n takes Θ(n) time.
That linear merge is the whole reason the algorithm reaches O(n log n): there are log n levels of splitting, and each level costs Θ(n) to recombine.
- Split at the midpoint; recurse on both halves
- Length 0 or 1 is the base case — already sorted
- The merge compares only the front of each run
- Merging two runs is linear in their combined length
Why It Is Always O(n log n)
Halving repeatedly reaches length 1 after log₂ n levels. At each level, every element belongs to exactly one merge, so the total work per level is Θ(n) — the merges are smaller further down, but there are proportionally more of them.
Multiplying gives Θ(n log n), and the recurrence T(n) = 2T(n/2) + Θ(n) confirms it by the master theorem.
The crucial property is that this holds on every input. The split is positional, not value-dependent — the midpoint does not care what the data looks like — so sorted, reversed, and random arrays all cost the same. Compare quick sort, whose split depends on a pivot and degrades to O(n²) when that pivot is chosen badly. When you need a guarantee rather than a good average, this is why merge sort is the answer.
| Best | Average | Worst | Space | |
|---|---|---|---|---|
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) |
- log n levels because the length halves each time
- Θ(n) work per level, whatever the data
- The split is positional, so no input can unbalance it
- T(n) = 2T(n/2) + Θ(n) solves to Θ(n log n)
Sort with merge sort
def merge_sort(values):
if len(values) <= 1: # a run of 0 or 1 is already sorted
return values
mid = len(values) // 2
left = merge_sort(values[:mid])
right = merge_sort(values[mid:])
return merge(left, right)
def merge(left, right):
merged, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= keeps the sort stable
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged.extend(left[i:]) # one run is empty; copy the rest
merged.extend(right[j:])
return merged
print(merge_sort([38, 27, 43, 3]))
#include <iostream>
#include <vector>
std::vector<int> merge(const std::vector<int>& left,
const std::vector<int>& right) {
std::vector<int> merged;
merged.reserve(left.size() + right.size());
std::size_t i = 0, j = 0;
while (i < left.size() && j < right.size()) {
if (left[i] <= right[j]) merged.push_back(left[i++]); // <= is stable
else merged.push_back(right[j++]);
}
while (i < left.size()) merged.push_back(left[i++]);
while (j < right.size()) merged.push_back(right[j++]);
return merged;
}
std::vector<int> mergeSort(const std::vector<int>& values) {
if (values.size() <= 1) return values;
const std::size_t mid = values.size() / 2;
return merge(mergeSort({values.begin(), values.begin() + mid}),
mergeSort({values.begin() + mid, values.end()}));
}
int main() {
for (int v : mergeSort({38, 27, 43, 3})) std::cout << v << ' ';
std::cout << '\n';
}import java.util.Arrays;
public class MergeSort {
static int[] mergeSort(int[] values) {
if (values.length <= 1) return values; // 0 or 1 is already sorted
int mid = values.length / 2;
int[] left = mergeSort(Arrays.copyOfRange(values, 0, mid));
int[] right = mergeSort(Arrays.copyOfRange(values, mid, values.length));
return merge(left, right);
}
static int[] merge(int[] left, int[] right) {
int[] merged = new int[left.length + right.length];
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) merged[k++] = left[i++]; // <= is stable
else merged[k++] = right[j++];
}
while (i < left.length) merged[k++] = left[i++];
while (j < right.length) merged[k++] = right[j++];
return merged;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(mergeSort(new int[]{38, 27, 43, 3})));
}
}Step through it
Running on [38, 27, 43, 3]
On paper: One Merge Step
The recursion is easy to state and easy to get vague about, so trace a single merge concretely. Take the two sorted runs [27, 38] and [3, 43], with index i on the left run and j on the right:
- Compare 27 and 3 take 3, and
jadvances. Output[3]. - Compare 27 and 43 take 27, and
iadvances. Output[3, 27]. - Compare 38 and 43 take 38, and
iadvances. Output[3, 27, 38]. - Left run empty copy the rest of the right run wholesale: 43. No comparison needed. Output
[3, 27, 38, 43]. - Cost 3 comparisons for 4 elements. Merging runs of length a and b takes at most a + b − 1.
Two details earn marks. First, when one run empties you copy the rest of the other directly — no more comparisons are needed, because it is already sorted. Second, the merge used 3 comparisons for 4 elements: merging two runs of length a and b needs at most a + b − 1 comparisons, and fewer when one run drains early.
- Two indices, one per run; compare only the fronts
- The smaller front is always the next output value
- When one run empties, copy the remainder without comparing
- At most a + b − 1 comparisons to merge runs of length a and b
Stability and the Space Cost
Merge sort is stable, but only because of one deliberate choice: on a tie, take from the left run. Writing if (left[i] <= right[j]) preserves original order among equal keys; writing < instead silently breaks stability, and this is the single most common bug in a hand-written merge.
The real cost is memory. The merge cannot be done in place without heavy machinery, so the standard implementation allocates an O(n) buffer. Allocating one buffer up front and reusing it across all merges is markedly faster than allocating inside each recursive call.
That space requirement is what keeps merge sort out of memory-constrained code, where heap sort gives the same O(n log n) guarantee in O(1) space. On linked lists the calculus flips completely: merging is pure pointer relinking, needs no extra array, and merge sort becomes the natural list-sorting algorithm.
- Take from the left run on ties, or stability is lost
- Allocate the scratch buffer once and reuse it
- O(n) auxiliary space is the main trade against quick sort
- On linked lists it needs only O(log n) stack and no buffer
Where It Is Actually Used
Merge sort underpins more production code than its textbook reputation suggests. Timsort — the default sort in Python and for objects in Java — is a merge sort that first detects naturally occurring sorted runs and merges those, which makes it O(n) on already-sorted input while keeping the O(n log n) guarantee.
It is also the standard approach to external sorting: when data exceeds memory, sort chunks that fit, write them out, then merge the sorted files with a k-way merge that only ever holds one block per file. Sequential access is exactly what merge sort needs and what disks reward.
In parallel settings the independent halves are natural work units, and merges combine cleanly across threads. If you need stability, predictability, or you are sorting objects by a key, merge sort is the default; reach for quick sort only when in-place speed on primitives matters more than the guarantee.
- Timsort adds run detection to plain merge sort
- External sorting merges sorted chunks that do not fit in memory
- Sequential access patterns suit disks and prefetchers
- Choose it when stability or a hard guarantee is required