Two sorted lines zipped together
Merge Sort
The analogy
Split the line in half, and again, until every group is one kid — a group of one is already sorted. Then zip pairs of sorted groups back together by repeatedly taking the shorter kid from the front of either group. Splitting is free; the zipping does the work.
Visualizer
Watch it split and zip
step 1 / 475
3
8
1
9
2
7
4
8 numbers, out of order. Press play — or step through one comparison at a time.
📖 In depth — the full reference
The sorting scoreboard (for reference across all five sorting lessons)
| algorithm | best | average | worst | extra space | stable? |
|---|---|---|---|---|---|
| bubble | O(n) with early exit | O(n²) | O(n²) | O(1) | yes |
| selection | O(n²) — always | O(n²) | O(n²) | O(1) | no (long-range swaps) |
| insertion | O(n) on sorted input | O(n²) | O(n²) | O(1) | yes |
| 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²) (bad pivots) | O(log n) stack | no (typical) |
| Timsort (stdlib) | O(n) | O(n log n) | O(n log n) | O(n) | yes |
Merge sort — everything worth knowing
- Divide and conquer: split in half (log n levels), merge sorted halves (O(n) per level) → O(n log n) ALWAYS — no bad case exists. Determinism is its brand.
- The merge step is the whole trick: two sorted piles, compare the front cards, take the smaller — each element is touched once per level.
- Stable (take from the LEFT pile on ties) — which is why stdlib sorts descend from merge sort, not quicksort.
- The price: O(n) auxiliary memory for the merge scratch space. In-place merging exists but is grotesque; everyone pays the memory.
- Killer app — EXTERNAL sorting: data too big for RAM is sorted in chunks and merged from disk streams; merge only ever needs the FRONT of each pile in memory. Database ORDER BY on a billion rows is this.
- Recursion note: merge sort is the first algorithm here that NEEDS the recursion lesson — each half is "the same problem, smaller", trusted to the recursive call.
Python corner: heapq.merge — the merge step as a stdlib tool
import heapq logs_server_a = [1, 4, 9] # each already sorted (by timestamp) logs_server_b = [2, 3, 10] merged = list(heapq.merge(logs_server_a, logs_server_b)) print(merged) # [1, 2, 3, 4, 9, 10] # Lazy: works on generators/files without loading everything. # Merging k sorted streams at once is exactly how log aggregators work.
def merge_sort(a):
if len(a) < 2:
return a
mid = len(a) // 2
return merge(merge_sort(a[:mid]),
merge_sort(a[mid:]))
def merge(x, y):
out = []
while x and y:
out.append(x.pop(0) if x[0] <= y[0] else y.pop(0))
return out + x + yCheck yourself
Merge sort's worst case is…
Practice — write it yourself
The heart of merge sort: merge(a, b) zips two ALREADY-SORTED lists into one sorted list with a two-pointer walk. No sorted() allowed!
Python 3 · runs in your browser · your draft is saved locally
📝 My notessaved in this browser