How Merge Sort Works
Merge sort halves the array until each piece is trivially sorted, then merges the pieces back together in order. O(n log n) on every input, stable, and the reason it needs a second array.
- Waiting
- Being compared
- Just moved
- In final position
Step 1 of 50
Merge sort, 12 values in random order.
Counters
- Comparisons
- 0
- Writes
- 0
- n
- 12
- Average case
- O(n log n)
Settings
Two to 48 numbers. Sorted in exactly the order you type them.
Merge sort
- 1
width = 1 - 2
while width < n: - 3
for lo in 0..n step 2*width: - 4
mid = lo + width - 5
hi = lo + 2*width - 6
// merge a[lo..mid) and a[mid..hi) - 7
take the smaller head each time - 8
width *= 2
The same array, every algorithm
Comparisons on the values above, cheapest first. Writes in the second line. Run it on nearly sorted values to see the O(n log n) sorts lose.
- Merge3344 writes
- Quick3340 writes
- Insertion4042 writes
- Shell4637 writes
- Heap5166 writes
- Bubble6062 writes
- Selection6618 writes
How the seven compare
| Algorithm | Best | Average | Worst | Extra memory | Stable |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No |
| Shell | O(n log n) | O(n√n) | O(n²) | O(1) | No |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
Stable means equal values keep their original order.
Complexity
| Best | Average | Worst | Extra memory |
|---|---|---|---|
| O(n log n) | O(n log n) | O(n log n) | O(n) |
The O(n) buffer is the trade: an in-place merge exists but is slow enough in practice that nobody uses it.
How merge sort works
Merge sort splits the array in half, sorts each half the same way, and then merges the two sorted halves by repeatedly taking the smaller of their two front elements. The splitting gives log n levels and each level touches every element once, so the running time is n log n on every input — best case, worst case and average alike.
- Split the range in half. Keep splitting until each piece holds one element, which is sorted by definition.
- Merge two sorted pieces: compare their front elements and copy the smaller one out, advancing that side.
- When one side runs dry, copy the rest of the other side across unchanged.
- Merge upward level by level until one sorted run covers the whole array.
Implementation
The same algorithm the visualiser is running, written to be read.
def merge_sort(values):
if len(values) <= 1:
return values
middle = len(values) // 2
left = merge_sort(values[:middle])
right = merge_sort(values[middle:])
merged, i, j = [], 0, 0
while i < len(left) and j < len(right):
# <= rather than <, so equal values keep their original order.
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return mergedWhen to use it
- Use it when stability matters — equal elements keep their original order, which is what makes sorting by one field then another work.
- Use it for linked lists, where splitting and merging need no extra memory at all and no random access.
- Use it for data that does not fit in memory: the merge step reads sequentially, which is why external sorts are merge sorts.
- Avoid it when memory is tight and stability is not needed; heapsort gets the same guarantee in O(1) space.
Check yourself
If the animation made sense, these should too.
Which comparison in the merge makes it stable, and how?
Taking from the left run when the two fronts are equal - `left[i] <= right[j]`. Equal elements from the earlier half are emitted first, so their original relative order survives. Changing that to `<` makes the sort unstable without changing its speed.
Why is merge sort the algorithm of choice for data that does not fit in memory?
Because the merge step reads both inputs strictly sequentially and writes its output sequentially. Sequential access is what disks and network streams are good at, and it means the algorithm never needs more than a block of each run in memory at once.