Sorting Data That Doesn't Fit
In short: every sort so far assumed the whole array lives in memory at
once. When the data is bigger than RAM, that assumption breaks, and disk
reads become the real cost — not comparisons. External sorting splits the
data into chunks small enough to sort in memory (runs), writes each run
back to disk, then merges all the runs in one pass using a min-heap that
never holds more than one item per run at a time. The heap from the heap
sort lesson comes back here for a different job: picking the smallest of k
candidates, cheaply, over and over.
Watch the merge phase pop the smallest item across three runs, one pass, no re-reading:
Each heappush/heappop costs O(log k) for k runs, and the merge visits
every item exactly once — O(n log k) total, a single sequential pass over
the data instead of n passes of "find the overall minimum".
Sort a batch bigger than memory
Quarry's compactor ingests more records overnight than fit in memory. Split, sort each piece, then merge — the runs never need to be loaded all at once during merging, only their current front item:
With memory_limit = 3 on 9 items, that's 3 runs of 3 — each small enough to
sort with any in-memory sort, then merged with a heap of size 3, never size
9.
When there are too many runs to merge at once
If there are more runs than the heap can hold open file handles for, merge
happens in passes: merge k runs at a time into fewer, bigger runs,
repeat, until one remains. The number of passes is 1 + ⌈log_k(runs)⌉ — the
1 is run generation, and each merge pass divides the run count by k:
import math
def merge_pass_count(num_runs, fan_in):
if num_runs <= 1:
return 1
return 1 + math.ceil(math.log(num_runs, fan_in))
print(merge_pass_count(64, 4), merge_pass_count(64, 8))A wider merge means fewer total passes, which is why real external sorts (and database engines) use as many open runs per merge as memory allows, not a fixed small number.
Quick practice
import heapq
runs = [[10, 40], [20, 30, 50]]
heap = [(run[0], r, 0) for r, run in enumerate(runs)]
heapq.heapify(heap)
value, r, idx = heapq.heappop(heap)
print(value, r)IndexErrorThis crashes instead of printing the sorted list. Fix the off-by-one in the guard before pushing a run's next item.
🎯 Your turn
Build external_sort(data, memory_limit): return data fully sorted
ascending, by splitting it into chunks of at most memory_limit items
(sorted individually — "run generation"), then merging every run in one pass
with a min-heap ("k-way merge").
external_sort([5, 3, 8, 1, 9, 2, 7, 4, 6], 3)→[1, 2, 3, 4, 5, 6, 7, 8, 9]external_sort([], 3)→[]
Hint: push (run[0], run_index, 0) for every non-empty run onto a heap.
Pop the smallest, append its value to the output, and if that run has a next
item, push (run[idx + 1], run_index, idx + 1).
Press ▶ Run, try the Live App chips, then ✓ Check.