Merge Sort —
A real algorithm built entirely from recursion.
Every recursion lesson so far has used toy examples — merge sort is the first one that's a genuinely useful algorithm, and it's built from the same two-halves pattern: split down to single elements (the base case), then merge pairs back together on the way up. Watch the split-then-merge call tree unfold on LearnBug from the recursion side, not just the sorting side.
What makes Merge Sort recursive?
merge_sort(arr) splits the array in half, recursively sorts each half, then merges the two sorted halves back together. The base case is an array of 0 or 1 elements — already sorted, nothing to do. The recursive case always operates on a strictly smaller array, so it's guaranteed to reach the base case.
Why visualization helps
Merge sort has two distinct recursive calls per level — for the left half and the right half — plus a separate merge step that only runs after both return. Watching the split happen all the way down to single elements, then the merge happen on the way back up, makes the "divide, conquer, combine" pattern concrete instead of a phrase to memorize.
The three-part pattern behind merge sort
Divide — split in half, recursively
Every recursive call splits its array into two halves and calls itself on each. This continues until arrays reach length 0 or 1 — the base case.
Conquer — the base case is trivial
A single element (or empty array) is already sorted by definition — no work needed, just return it as-is.
Combine — merge two sorted halves
This is the real work, and it happens on the way back up: given two already-sorted arrays, walk them together and build one sorted result in O(n) time.
merge_sort([5, 2, 8, 1, 9, 3]) — the recursion tree
Split repeatedly: [5,2,8,1,9,3] → [5,2,8] & [1,9,3] → down to single elements
Every call splits its array in half and recurses on each half — no merging happens yet. This continues until every array has exactly one element, which is trivially sorted.
Merge starts bottom-up: [5] and [2] merge into [2, 5]; [1] and [9] merge into [1, 9]
This is the first real work in the whole algorithm. Merging two single elements just means comparing them and putting the smaller one first.
[2,5] merges with [8] → [2,5,8]; [1,9] merges with [3] → [1,3,9]
Merging a sorted 2-element array with a single element walks both from the front, comparing and taking the smaller each time — [2,5] vs [8]: 2, then 5, then 8 (8 is bigger than both).
Final merge: [2,5,8] and [1,3,9] combine into one fully sorted array
Compare 2 vs 1 → take 1. Compare 2 vs 3 → take 2. Compare 5 vs 3 → take 3. Compare 5 vs 9 → take 5. Compare 8 vs 9 → take 8. Only 9 remains → take 9.
Return: [1, 2, 3, 5, 8, 9] ✓ log₂(6) ≈ 3 levels of splitting, 3 levels of merging
Split, recurse, merge
def merge_sort(arr):
if len(arr) <= 1: # base case — already sorted
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # recursive case — sort the left half
right = merge_sort(arr[mid:]) # recursive case — sort the right half
return merge(left, right) # combine — the actual work
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:]) # append whatever's left over
result.extend(right[j:])
return result
print(merge_sort([5, 2, 8, 1, 9, 3]))Complexity Notes
Frequently asked questions
Why does splitting in half give O(log n) levels?
Each level of recursion halves the array size — n, n/2, n/4, ... down to 1. The number of times you can halve n before reaching 1 is log₂(n), which is exactly the recursion depth, and also exactly how many "merge levels" happen on the way back up.
Where does the O(n) work per level come from?
At any single level of the recursion tree, all the merge calls combined touch every element exactly once — merging is a linear walk through both halves. Summed across one full level, that's O(n) work, and there are O(log n) levels, giving O(n log n) total.
Is merge sort's recursion the same shape as Fibonacci's?
Both make two recursive calls per frame, but merge sort's calls operate on genuinely disjoint halves of the input — no overlap, no duplicate work. That's exactly why merge sort is O(n log n) while naive Fibonacci is O(2ⁿ): Fibonacci's two branches recompute overlapping subproblems, merge sort's don't.
Why does the merge step need extra arrays instead of sorting in place?
Merging two sorted sequences by comparing their fronts naturally builds a brand new sequence — you can't easily overwrite either input array in place while still reading from both of them correctly. This is the direct cause of merge sort's O(n) space cost, in contrast to quick sort's in-place partitioning.
Watch the array split all the way down, then merge back up
Paste merge sort into LearnBug and see the full divide-and-conquer recursion tree.