The Story That Explains Merge Sort
Now the magic flows back up. Each pair of helpers merges their two tiny sorted stacks into one larger sorted stack, simply by repeatedly taking whichever top paper has the smaller ID. Pair by pair, the sorted stacks combine—2, then 4, then 8—until the teacher receives one perfectly ordered pile of 400.
That cascade of split-down then merge-up is exactly Merge Sort.
Merge Sort is the textbook divide-and-conquer algorithm. It splits the array in half, recursively sorts each half, then merges the two sorted halves into one. Because a list of one element is already sorted, the recursion always bottoms out — and the merging does the real work. It guarantees O(n log n) time in every case and is stable.
Merging two already-sorted lists is cheap — one linear pass with two pointers. Merge Sort leans entirely on that fact: break the problem down until sorting is trivial, then spend all the effort on cheap merges as you build back up.
Divide, Conquer, Combine
Every divide-and-conquer algorithm has three moves. Merge Sort's are unusually clean.
Every call halves its segment and recurses — the tree is about log₂n levels deep. The amber leaves are single elements, which are sorted by definition, so the recursion stops there.
The two halves are already sorted, so we only ever look at their front elements. Each comparison copies exactly one value into the result — making a full merge cost just O(n).
In the merge step, when the front elements tie, Merge Sort always takes the one from the
left half first (left[i] <= right[j]). Since the left half held
the earlier-occurring elements, their original order is preserved — that is what makes
Merge Sort stable, and why Python's TimSort and Java's Collections.sort
are built on it.
How It Works — Step by Step
Hands-On — Watch Each Line Do Its Job
Press Step (or Auto) and follow along: the highlighted code line is executing right now, the phase tag tells you whether we are dividing or merging, the bars show the array, and during a merge the Left / Right rows reveal the two pointers comparing and copying elements.
During DIVIDE (blue/purple bars) nothing gets sorted — the array just keeps halving. All the ordering happens during MERGE: line 14 compares the two pointer elements, lines 15/17 copy the smaller one back into the array (it turns green), and the leftovers get flushed by lines 20/22. The deepest, smallest merges finish first; the full-array merge happens last.
The Recursion Tree, as a Table
Here is the same run on [38, 27, 43, 3, 9, 82]. Read it top-down for the
divide, then bottom-up for the merge.
| Level | Divide (splitting down) | Merge (combining up) |
|---|---|---|
| 0 | [38, 27, 43, 3, 9, 82] | [3, 9, 27, 38, 43, 82] |
| 1 | [38, 27, 43] | [3, 9, 82] | [27, 38, 43] | [3, 9, 82] |
| 2 | [38] [27, 43] | [3] [9, 82] | [38] [27, 43] | [3] [9, 82] |
| 3 | [38] [27] [43] [3] [9] [82] | single elements — already sorted |
| Step | Action |
|---|---|
| 1 | Split 6 → 3 + 3 |
| 2 | Split 3 → 1 + 2 |
| 3 | Split 2 → 1 + 1 |
| 4 | Stop: size 1 |
| Step | Action |
|---|---|
| 1 | Merge [27]+[43] → [27,43] |
| 2 | Merge [38]+[27,43] → [27,38,43] |
| 3 | Merge [9]+[82], [3]+… |
| 4 | Merge halves → full sort |
Full Python Implementation
Clean Recursive Version (returns a new list)
def merge_sort(arr):
# Base case: 0 or 1 element is already sorted
if len(arr) <= 1:
return arr
# 1. DIVIDE — split at the midpoint
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # 2. CONQUER — sort left half
right = merge_sort(arr[mid:]) # CONQUER — sort right half
return merge(left, right) # 3. COMBINE
def merge(left, right):
result = []
i = j = 0
# Walk both pointers, taking the smaller front element
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= keeps it STABLE
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
# One side is empty — flush the remaining sorted tail
result.extend(left[i:])
result.extend(right[j:])
return result
# ── Demo ──────────────────────────────────────────────
data = [38, 27, 43, 3, 9, 82]
print("Before:", data)
print("After: ", merge_sort(data))In-Place Index Version (the one animated above)
This variant sorts arr[lo:hi] in place by writing merged values back into the same
indices — closer to how production libraries minimise allocations.
def merge_sort(arr, lo=0, hi=None):
if hi is None:
hi = len(arr)
if hi - lo <= 1:
return
mid = (lo + hi) // 2
merge_sort(arr, lo, mid)
merge_sort(arr, mid, hi)
left, right = arr[lo:mid], arr[mid:hi]
i = j = 0; k = lo
while i < len(left) and j < len(right):
if left[i] <= right[j]:
arr[k] = left[i]; i += 1
else:
arr[k] = right[j]; j += 1
k += 1
while i < len(left): arr[k] = left[i]; i += 1; k += 1
while j < len(right): arr[k] = right[j]; j += 1; k += 1Inside the Merge — The Two-Pointer Trick
Merging [27, 38, 43] with [3, 9, 82]. Two pointers, always compare the fronts,
copy the smaller, advance that pointer.
27 vs 3 → take 3 from right. Result: [3]
27 vs 9 → take 9 from right. Result: [3, 9]
27 vs 82 → take 27 from left. Result: [3, 9, 27]
38 vs 82 → take 38. Result: [3, 9, 27, 38]
43 vs 82 → take 43. Left now empty.
[82] copied as-is → [3, 9, 27, 38, 43, 82]
Each comparison consumes exactly one element from one of the halves, so a merge of two halves with
n elements total takes at most n copies. The whole array has
log n levels of merging, each costing O(n) — giving the famous
O(n log n).
Complexity — The Same Speed, Every Time
Merge Sort solves T(n) = 2·T(n/2) + O(n): two half-size sub-problems plus a
linear merge. By the Master Theorem this resolves to:
Time = O(n log n) — best, average AND worst
Space = O(n) — auxiliary array for merging
That guaranteed worst case is its superpower: unlike quicksort, no input can ever degrade it to
O(n²).
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
Merge Sort's clean recursion costs O(n) extra memory for the temporary arrays, plus recursion-stack overhead. On memory-constrained systems, or when you need true in-place sorting, quicksort or heapsort can be preferable — and for tiny inputs, insertion sort's low overhead wins.
When To Use Merge Sort (and When Not To)
Benefits at a Glance
Golden Rules
<=, not <, in the merge comparison. Taking the left
element on ties is what makes the sort stable. Flip it and you silently lose stability.
while loops must copy them, or you drop data.