External Sorting, Merge Strategies, and Parallel Sort (TAOCP Vol. 3) — The Real Bottleneck in Indexer Rebuilds TODO
Concept
External sorting is used when data doesn't fit in memory: it splits into a run-generation phase, where memory-sized runs are sorted and written to disk, and a merge phase, where those runs are combined via k-way merging. Raising the merge fan-in k shrinks the number of passes needed — it's log base k of the number of runs — but each run needs its own input buffer, so a bigger k means smaller per-run buffers and worse sequential-read efficiency; that's the tradeoff. Using replacement selection during run generation can produce runs longer than memory on average, which cuts the number of runs outright. Parallel sorting either splits the data, sorts each part, and merges, or uses sample sort — sampling to pick partition boundaries and sorting each partition independently — and in both cases the real bottleneck is memory bandwidth and data movement, not comparisons. In other words, the cost model for external and parallel sorting should be built on blocks and bytes transferred, not comparison count.
Sorts that exceed memory come up constantly in practice — index rebuilds, large joins, log reprocessing — and what actually decides performance there is buffer size and merge fan-in, not algorithm choice.
Code & Formula
# 외부 정렬 — 메모리에 다 못 올리는 데이터를 런(run)으로 쪼개 정렬 후 k-way 병합한다.
# 비용은 비교 횟수가 아니라 "몇 번 디스크를 훑는가(패스 수)"로 세는 게 핵심이다.
import heapq
import random
random.seed(1)
data = random.sample(range(1000), 37) # "디스크에 있는" 전체 데이터
MEMORY_CAPACITY = 6 # 메모리에 한 번에 올릴 수 있는 크기
def make_sorted_runs(data, capacity):
runs = []
for i in range(0, len(data), capacity):
chunk = data[i:i + capacity]
runs.append(sorted(chunk)) # 런 하나 = 메모리에 올려 정렬 후 "디스크"에 기록
return runs
def k_way_merge(runs):
# heapq.merge 는 여러 정렬된 이터러블을 O(N log k) 로 병합한다 (k = 런 개수)
return list(heapq.merge(*runs))
runs = make_sorted_runs(data, MEMORY_CAPACITY)
merged = k_way_merge(runs)
import math
num_passes = math.ceil(math.log(len(runs), MEMORY_CAPACITY)) if len(runs) > 1 else 1
print("input size:", len(data), "| memory capacity:", MEMORY_CAPACITY)
print("number of sorted runs:", len(runs))
for i, r in enumerate(runs):
print(f" run {i}: {r}")
print("merged result is sorted:", merged == sorted(data))
print("approx merge passes needed (log_k of run count):", num_passes)
docs/code/algorithms/algorithms-80.py
Exercise
Implement external sort over a file larger than memory using a fixed buffer, then vary the merge fan-in and measure total runtime and actual bytes read/written to find the optimum.
Practical Connection
Re-indexing chain events from genesis makes sorting block/log keys a real bottleneck, and tuning batch size and merge fan-in there determines the total re-sync time.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.