Merge sort splits the array in half, sorts each half the same way, then merges the two sorted halves into one. The merge is the only real work: put a pointer at the front of each half and keep taking whichever value is smaller.
Press play, or step through it. Orange is the pair being compared, one from each run. The row underneath is the merged output being built up, and it sits directly under the positions it will be copied back into. Green is a run that is in order.
Ready. 8 values, unsorted.
0 comparisons · 0 writes
Ready. 8 values, unsorted.
- Comparing
- Writing back
- Sorted run
Code
- def merge_sort(a, lo=0, hi=None):
- if hi is None:
- hi = len(a) - 1
- if lo >= hi:
- return a
- mid = (lo + hi) // 2
- merge_sort(a, lo, mid)
- merge_sort(a, mid + 1, hi)
- merged = []
- i, j = lo, mid + 1
- while i <= mid and j <= hi:
- if a[i] <= a[j]:
- merged.append(a[i])
- i += 1
- else:
- merged.append(a[j])
- j += 1
- merged += a[i:mid + 1]
- merged += a[j:hi + 1]
- a[lo:hi + 1] = merged
- return a
Watch the first few steps go nowhere: merge sort halves the array down to single
values before it merges anything, and depth in the status line tells you how far
down it currently is. Then try Sorted and Reversed. Both cost 12 comparisons
and 24 writes on these eight values, because neither one changes how many times
the array gets halved. That flatness is the whole selling point.
Time and space complexity
| Case | Complexity | Why |
|---|---|---|
| Best | O(n log n) | Already sorted. Each merge empties one run early, but the splitting still happens. |
| Average | O(n log n) | log n levels of halving, n values merged at each level. |
| Worst | O(n log n) | The same. No input makes merge sort slower. |
| Space | O(n) | The merge buffer holds the slice being merged, plus O(log n) stack frames. |
| Stable | Yes | Ties are taken from the left run, so equal values keep their input order. |
There is no early exit here, and that is the trade. Bubble sort can finish an
already sorted array in O(n); merge sort cannot beat O(n log n) on anything.
What it gets in return is that it never does worse either.
Step by step
- If the slice holds fewer than two values, it is already sorted. Return it.
- Otherwise find the midpoint and split into a left half and a right half.
- Sort the left half with this same procedure.
- Sort the right half with this same procedure.
- Merge them. Put a pointer at the front of each half, compare the two values, take the smaller one, and advance that pointer. On a tie, take the left one.
- When one half runs out, append everything left in the other. No comparisons needed — those values are already in order and larger than everything taken.
- Copy the merged run back over the slice it came from.
Steps 3 and 4 are the recursion, and they are why the animation appears to stall at the start. Nothing visible happens until a merge at step 5 has two sorted runs to work with.
Worked example
Sorting [8, 3, 5, 1]:
| Step | Array after | What happened |
|---|---|---|
| Split | [8, 3, 5, 1] | Positions 0–3 halve into 0–1 and 2–3, then each of those halves again into single values. |
| Merge 0–1 | [3, 8, 5, 1] | Compare 8 and 3, take 3. The right run is now empty, so 8 follows for free. 1 comparison. |
| Merge 2–3 | [3, 8, 1, 5] | Compare 5 and 1, take 1, then 5 follows. 1 comparison. |
| Merge 0–3 | [1, 3, 5, 8] | Compare 3 and 1 take 1, compare 3 and 5 take 3, compare 8 and 5 take 5, then 8 follows. 3 comparisons. |
Five comparisons and eight writes. Bubble sort
does the same four values in six comparisons, which is the honest picture at this
size: the gap only opens up as n grows, because one side of it is n² and the
other is n log n.
When to use it
| Reach for it when | Avoid it when |
|---|---|
You need a guaranteed O(n log n), whatever the input looks like | Memory is tight — it wants a buffer the size of the array |
| Equal values must keep their original order | You want the fastest in-place sort and can accept a bad worst case; that is quicksort |
| The data is too big for memory and you are merging sorted chunks off disk | The array is small enough that insertion sort's lower overhead wins |
| You are sorting a linked list, where merging needs no extra array at all | You need no recursion and no allocation whatsoever |
The code
Every version below is top-down, merges into a buffer, and takes ties from the left, so the complexity table above holds whichever one you read.
def merge_sort(a, lo=0, hi=None):
if hi is None:
hi = len(a) - 1
if lo >= hi:
return a
mid = (lo + hi) // 2
merge_sort(a, lo, mid)
merge_sort(a, mid + 1, hi)
merged = []
i, j = lo, mid + 1
while i <= mid and j <= hi:
if a[i] <= a[j]:
merged.append(a[i])
i += 1
else:
merged.append(a[j])
j += 1
merged += a[i:mid + 1]
merged += a[j:hi + 1]
a[lo:hi + 1] = merged
return a
nums = [5, 1, 4, 2, 8]
merge_sort(nums)
print(nums)
Common questions
What is the time complexity of merge sort?
O(n log n) in the best, average and worst case. Halving the array gives log n levels, and every level merges all n values. For an array of 2^k values the worst case is exactly n log₂ n − n + 1 comparisons, so eight values never cost more than 17.
Is merge sort stable?
Yes, as long as ties are taken from the left run. The comparison is a[i] <= a[j], so when two values are equal the one that started further left is written first. Change that to a strict < and merge sort stops being stable.
Why is merge sort O(n log n) even on sorted input?
Because the splitting never looks at the data. Bubble sort can notice a clean pass and stop early; merge sort halves the array all the way down regardless, then merges back up. Sorted input makes each merge cheaper — one run empties early and the rest is copied without comparisons — but the number of levels does not change.
How much extra memory does merge sort need?
O(n). Merging two runs needs somewhere to put the output, and that buffer is as large as the slice being merged. On top of that the recursion costs O(log n) stack frames. In-place merge variants exist but they trade a lot of speed for the memory, so they are rarely worth it.
Merge sort or quicksort?
Quicksort is usually faster in practice: it sorts in place and its memory access pattern is kinder to the cache. But its worst case is O(n²) and it is not stable. Merge sort guarantees O(n log n) on every input and preserves the order of equal values, and it costs O(n) memory for that guarantee. Java makes exactly this trade both ways — quicksort for primitive arrays, a merge-based sort for objects, where stability is part of the contract.
Is merge sort used in real code?
Yes, though usually in a smarter form. Python's sorted and Java's Arrays.sort for objects both use stable merge-based algorithms in the Timsort family, which find runs that are already in order and merge those instead of splitting down to single values. Merge sort is also the standard way to sort data too large for memory: sort chunks, write them out, then merge the sorted files.