Merge Sort & Library Merge
A listener signs in on a new laptop. Their phone library is sorted A→Z, and so is the laptop's. Gluing them together and sorting again would throw away the order you already have. Merging walks the two fronts once and is done — and that one step, applied recursively, sorts anything in O(n log n): merge sort.
Divide and conquer
Merge sort is the classic divide-and-conquer algorithm:
- Divide — split the list into two halves.
- Conquer — sort each half, by calling merge sort on it (recursion).
- Combine — merge the two sorted halves into one.
The base case is a list of 0 or 1 items: already sorted. Here is just the dividing, so you can see the shape it makes:
Every call hands its two halves to itself — the tree-shaped recursion from the recursion lesson, with lists instead of playlists.
The merge step
Two sorted lists, two pointers. Compare the fronts, take the smaller, advance that pointer. When one list runs out, everything left in the other is already in order — copy it across.
The comparisons stop the moment either list is empty:
def merge_comparisons(a, b):
i = j = count = 0
while i < len(a) and j < len(b):
count += 1
if a[i] <= b[j]:
i += 1
else:
j += 1
return count
print(merge_comparisons([1, 2, 3], [4, 5, 6]))Forget that copy and the tail of the longer list silently disappears:
This should print all five titles in order. It prints three — "Dawn" and "Glow" are lost when the second list runs out.
Merge sort
Put the pieces together: split, sort both halves recursively, merge.
calls = 0
def split_only(items):
global calls
calls += 1
if len(items) <= 1:
return items
mid = len(items) // 2
return split_only(items[:mid]) + split_only(items[mid:])
split_only([8, 3, 5, 1, 7, 2, 6, 4])
print(calls)Why it's O(n log n)
Look at the split tree level by level. The top level merges n items. The next level merges two lists of n/2 — n items again. Every level touches all n items once, and halving reaches size 1 after log₂ n levels. So: n work × log n levels.
Doubling n now slightly more than doubles the work, instead of quadrupling it. And unlike the elementary sorts, the input order barely matters: sorted, reversed or random, it's O(n log n) every time.
The price: O(n) extra space
Every merge builds a new list, and the slices items[:mid] copy too. At any
moment merge sort holds O(n) extra items, plus O(log n) stack frames — the
recursion is only as deep as the split tree is tall.
❓ Cross-question — "Can't merge sort work in place, like insertion sort?" Not practically. In-place merging exists, but it's intricate and slower. That extra memory is the real trade-off — and the reason quick sort, next lesson, is still in business.
Stability comes from one character
When the fronts tie, <= takes from the left list — the one that came
first in the original order. So equal items never swap: merge sort is stable.
Change it to < and ties take from the right:
left = [("Echo", 5)]
right = [("Aria", 5)]
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i][1] < right[j][1]:
out.append(left[i])
i += 1
else:
out.append(right[j])
j += 1
out += left[i:] + right[j:]
print([title for title, plays in out])| operation | time | extra space | stable |
|---|---|---|---|
| merge two sorted lists (n + m items) | O(n + m) | O(n + m) | yes, with <= |
| merge sort — best, average, worst | O(n log n) | O(n) + O(log n) stack | yes |
| insertion sort, for comparison | O(n) to O(n²) | O(1) | yes |
Idioms & real-world patterns
heapq.merge — merging without building lists
The standard library merges any number of sorted inputs lazily, yielding one item at a time:
Timsort already knows this trick
Python's sorted() is Timsort — a merge-sort hybrid. It spots runs that are
already in order, so sorted(phone + laptop) finds two runs and merges them in
roughly linear time. In production that one-liner is fine; the hand-written merge
is for when you're building the sort, or the data doesn't fit in memory.
Coming from Java/JS: Java's
Collections.sortandList.sortare TimSort too, and V8'sArray.prototype.sortswitched to TimSort in 2018. Merge sort is the sort you've been calling all along.
⚡ Advanced — bottom-up merge sort, no recursion
Skip the splitting: treat every item as a sorted run of 1, merge neighbouring pairs into runs of 2, then 4, then 8 — until one run is left.
⚡ Advanced — external sorting
A library too big for memory is sorted the same way: sort chunks that do fit,
write each to disk, then merge all the sorted chunks in one streaming pass —
heapq.merge over open files. Databases sort this way.
🎯 Your turn
Write merge_libraries(a, b). Both lists of titles are sorted A→Z. Return one
A→Z list holding every title from both — a title in both libraries appears twice
— in a single pass with two pointers, not by re-sorting:
merge_libraries(["Aria", "Dawn", "Glow"], ["Blue", "Cove", "Echo"])→["Aria", "Blue", "Cove", "Dawn", "Echo", "Glow"]merge_libraries([], ["Blue"])→["Blue"]
Hint — compare a[i] with b[j], take the smaller (<= takes from a on a
tie), and when the loop ends, extend with whatever is left of both.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of Tunebox is built. ✅