Capstone: Quarry's Compactor
In short: Every lesson in this section answered one piece of "sort more, and sort it
smarter": heap sort's in-place O(n log n), non-comparison sorts that skip
comparing entirely, quickselect's one-sided search, the proof that no
comparison sort can do better than n log n in the worst case, and external
sorting's runs-then-merge shape for data bigger than memory. Quarry's
compactor is where the last piece — external sorting — becomes a real,
repeatable job: it doesn't just merge once, it keeps merging in rounds
until a growing batch of records collapses into a single sorted file, and it
reports exactly how many disk passes that cost.
What you're building
compactor(records, memory_limit, fan_in) -> {"sorted": [...], "runs": r, "passes": p}compactor([5, 3, 8, 1, 9, 2, 7, 4, 6], 3, 3)
# {"sorted": [1, 2, 3, 4, 5, 6, 7, 8, 9], "runs": 3, "passes": 2}sorted: every record, fully sorted ascending.runs: how many sorted runsrecordssplit into after generation —ceil(len(records) / memory_limit).passes: total disk passes — 1 for generation, plus one more per merge round, where each round foldsfan_inruns into one until a single run remains.
This is external sorting from the last lesson, generalized: instead of one
merge over every run at once, the compactor merges fan_in runs per round —
useful when there genuinely isn't room to hold every run's front item open at
the same time.
Generate, then round-robin merge
The same 9 records cost 2 passes with fan_in=3 and 3 passes with
fan_in=2 — a narrower merge always costs more disk passes for the same
data, which is exactly the tradeoff merge_pass_count measured in the last
lesson.
Why more memory (almost) always wins
Every one of Quarry's engines from this course trades memory for fewer disk
passes, and the compactor makes that trade explicit: a bigger memory_limit
means fewer, bigger runs after generation, and a bigger fan_in means fewer
merge rounds to collapse them:
def runs_needed(n, memory_limit):
import math
return 0 if n == 0 else math.ceil(n / memory_limit)
print(runs_needed(1000, 100), runs_needed(1000, 50))Quick practice
def passes_needed(num_runs, fan_in):
import math
return 1 if num_runs <= 1 else 1 + math.ceil(math.log(num_runs, fan_in))
print(passes_needed(27, 3))🎯 Your turn
Build compactor(records, memory_limit, fan_in): generate sorted runs
bounded by memory_limit, then repeatedly merge fan_in runs at a time
until one remains. Return {"sorted": [...], "runs": <runs after generation>, "passes": <total disk passes>}. Empty records → {"sorted": [], "runs": 0, "passes": 0}.
compactor([5, 3, 8, 1, 9, 2, 7, 4, 6], 3, 3)→{"sorted": [1, 2, 3, 4, 5, 6, 7, 8, 9], "runs": 3, "passes": 2}
Hint: generate_sorted_runs gives pass 1 and the runs count to report.
Then loop merge_round while more than one run remains, incrementing
passes each time — the final single run is the answer.
Press ▶ Run, try the Live App chips, then ✓ Check. Green = every piece of Quarry's ingest sorter is built. ✅