The merge is the whole algorithm
Merging two sorted arrays is linear. Keep a finger on the front of each; repeatedly take the smaller of the two and advance that finger. Merge [2, 5, 9] with [1, 6, 8]:
compare 2 vs 1 → take 1 [1]
compare 2 vs 6 → take 2 [1, 2]
compare 5 vs 6 → take 5 [1, 2, 5]
compare 9 vs 6 → take 6 [1, 2, 5, 6]
compare 9 vs 8 → take 8 [1, 2, 5, 8]
left only → append 9 [1, 2, 5, 6, 8, 9]
Six elements, five comparisons. Each comparison places exactly one element, so merging two runs of total length n costs at most n−1 comparisons and exactly n writes.
Where n log n comes from
Halving the array repeatedly gives log₂n levels of recursion — 32 elements become 16, 8, 4, 2, 1, which is 5 levels. At every level, the merges together touch all n elements exactly once. So:
total work = n per level × log2(n) levels = O(n log n)
The recurrence is T(n) = 2T(n/2) + O(n), which is the standard case of the master theorem giving Θ(n log n). Crucially this holds for every input — the split is positional, not value-dependent, so there is no bad pivot and no worst case. Sorted, reversed and random input all cost the same.
Split, sort, merge
Merge sort is divide and conquer in its cleanest form:
Divide. Split the array in half. Conquer. Sort each half recursively. Combine. Merge the two sorted halves.
The base case is an array of one element, which is sorted by definition. All the work is in the merge.
Sorting [38, 27, 43, 3]:
| Level | State |
|---|
| Split | [38, 27] [43, 3] |
| Split | [38] [27] [43] [3] |
| Merge | [27, 38] [3, 43] |
| Merge | [3, 27, 38, 43] |
The recursion has log n levels, and each level does O(n) work merging — hence O(n log n), for every input, with no bad cases.
Merging is the whole algorithm
Given two sorted lists, produce one sorted list by repeatedly taking the smaller of the two front elements:
def merge(left, right):
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= is what makes it stable
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
out.extend(left[i:]) # whatever remains is already sorted
out.extend(right[j:])
return out
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))
The <= on line 4 is not arbitrary. With <=, when two elements are equal the one from the left half is taken first — and since the left half came earlier in the original array, equal elements keep their relative order. That is stability, and changing <= to < silently destroys it.
Stability matters more than it sounds. Sorting a table by surname and then by department gives a list ordered by department, and alphabetical within each department — only if the second sort is stable.
Merging cannot be done in place without a substantial loss of simplicity or speed. The straightforward implementation allocates a new array at each merge, using O(n) additional memory.
That is merge sort's main disadvantage against quick sort, and it is what decides between them for in-memory array sorting.
| | Merge sort | Quick sort |
|---|
| Worst case | O(n log n) guaranteed | O(n²) |
| Extra space | O(n) | O(log n) |
| Stable | Yes | No |
| Cache behaviour | Good | Excellent |
| Linked lists | Ideal — O(1) extra | Poor — needs random access |
| External sorting | Ideal | Poor |
The linked-list row is worth noting: merging two linked lists requires only pointer rearrangement, so merge sort on a linked list uses O(1) extra space and is the natural choice there.
The guarantee, and what it costs
Merge sort's selling point is not that it is fast on average -- quick sort usually beats it -- but that its worst case equals its best case. Here is that guarantee measured against quick sort's on the input designed to break it, along with the price merge sort pays in memory.
Experiments to try
- Watch the recursion bottom out. Set Array Size to 16 and press Next Step repeatedly. The array splits until every block holds one element, and only then does anything get compared. All the sorting happens on the way back up.
- Count the levels. At Array Size 16 there are 4 levels of merging; at 32 there are 5. Doubling the array adds one level, and each level costs a full pass — that is n log n, split into its two factors.
- Give it sorted input. Press Randomize Array until the array is close to ascending and press Auto-Run. The step count barely moves. Unlike quick sort, merge sort has no input that hurts it.
- Spot the extra array. Watch a merge closely: elements are written to a separate buffer and then copied back. That buffer is the O(n) auxiliary memory, and it is not an implementation detail you can optimise away.
The memory cost, and why it is unavoidable
Merging in place is the hard part. To write the smaller element into position 0 you must first move whatever already occupies position 0, and doing that without a buffer requires shifting — which turns the linear merge quadratic.
So standard merge sort allocates an auxiliary array of size n, giving O(n) space. In-place merge sort algorithms exist, but they trade the clean linear merge for substantially worse constants and considerably more complexity. In practice, if memory is the constraint you use quick sort or heap sort instead.
The exception is linked lists, where merging needs only pointer reassignment and no buffer. Merge sort on a linked list is O(1) extra space, which is why it is the standard list-sorting algorithm.
Where this goes wrong
- Allocating a new buffer per recursive call. This turns O(n) space into O(n log n) and hammers the allocator. Allocate one buffer up front and pass it down.
- Breaking stability with < instead of ≤. When the two fronts are equal the merge must take from the left run. Using a strict comparison that prefers the right run reverses equal elements and silently destroys stability.
- Forgetting the leftover tail. When one run empties, the remainder of the other must be copied across. Dropping that step truncates the output.
- Recursing all the way to size 1. The call overhead dominates on tiny subarrays. Real implementations switch to insertion sort below roughly 16 elements, which typically buys 10–20%.
Key takeaway
Merge sort splits positionally, sorts recursively, and does its real work in a linear merge, giving a guaranteed Θ(n log n) on every input with no pathological case. It is stable, it parallelises cleanly, and it is the natural sort for linked lists and for data too large to fit in memory. The price is O(n) auxiliary space for arrays — which is precisely the trade quick sort makes in the opposite direction.
Where the guarantee earns its keep
External sorting. Data too large for memory is sorted by reading chunks, sorting each in memory, writing them back, and then merging the sorted runs in a streaming pass. Merge sort is the only classic algorithm whose access pattern is sequential enough for this, and it is how databases sort large results and how sort handles huge files.
Stability requirements. Multi-key sorting done as successive stable sorts, which is how spreadsheet and dataframe sorting works.
Linked lists. No random access needed, O(1) extra space.
Predictable latency. A guaranteed O(n log n) matters where a worst case would breach a service-level agreement, and quick sort's rare quadratic case is unacceptable.
Parallel sorting. The two halves are independent, so they can be sorted concurrently. Merge sort parallelises naturally in a way quick sort's in-place partitioning does not.
Timsort: what Python actually uses
Python's sorted and list.sort use Timsort, a merge sort adapted for real-world data. Two ideas make it faster than textbook merge sort:
It finds existing runs. Real data is often partially sorted, and Timsort detects ascending or descending runs and merges them rather than splitting down to single elements. On already-sorted input it is O(n).
It uses insertion sort for small runs. Below a threshold (32–64 elements), insertion sort's low constant factor beats recursion.
It is stable, which Python guarantees as part of the language, and its worst case remains O(n log n). Java uses it for object arrays for the same reasons.
The practical lesson: use the library sort. Timsort is better than anything you will write, and it handles the cases that matter.
Questions people ask
Why is merge sort O(n log n) always? Because the split is always exactly in half, independent of the data. Quick sort's split depends on the pivot, which is why its worst case differs.
Can merge sort be done in place? In-place variants exist and are considerably more complex and slower in practice. The O(n) space version is what is used.
Is merge sort stable? Yes, provided the merge takes from the left half on ties. That single comparison decides it.
Why does Python use Timsort rather than quick sort? Stability is a language guarantee, real data is often partially sorted, and the worst case is bounded.
Which is faster in practice? Quick sort, usually, on arrays in memory — better cache behaviour and no allocation. Timsort wins on partially-sorted data.
How does external merge sort work? Sort chunks that fit in memory, write them out, then merge the sorted runs with a k-way merge using a heap.
Recap in one screen
- Split in half, sort each half recursively, merge the sorted halves — O(n log n) for every input.
- All the work is in the merge, which takes the smaller front element repeatedly.
- Taking from the left half on ties is what makes it stable;
< instead of <= destroys that. - It needs O(n) extra space, which is its main cost against quick sort.
- Ideal for linked lists, external sorting and parallel sorting; Timsort is the production refinement.