External Sort & Large Queries

The problem, precisely

n items on disk, too large to fit in memory of size M (M ≪ n), need to end up fully sorted, also on disk. Disk I/O is orders of magnitude slower than RAM, so the metric that matters is number of passes over the data, not comparison count.

External merge sort — two phases

Phase	What happens
1. Sort in chunks	Read M-sized chunks, sort each in memory, write each sorted chunk back to disk — ⌈n/M⌉ sorted files
2. K-way merge	Min-heap holding the current smallest unconsumed value from each chunk file; pop, write to output, refill from that chunk — never load more than one block per chunk at a time

Write → memtable-sized chunks → sort each in RAM → k sorted files Merge → min-heap of k file pointers → pop smallest → write → refill

Phase 2 is the identical shape to merging k sorted linked lists, just with file handles instead of pointers. If the number of chunks exceeds how many file handles/heap entries you can hold open at once, merge in multiple rounds (B chunks per round) until one file remains — the pass count, roughly log_B(n/M), is the number engineers actually tune.

Where this shows up

Postgres ORDER BY. The work_mem setting caps how much memory one sort may use. Under the cap, Postgres sorts in memory; over it, it transparently falls back to external merge sort — visible directly via EXPLAIN (ANALYZE, BUFFERS): Sort Method: external merge Disk: NNNkB instead of Sort Method: quicksort Memory: NNNkB. A query that's mysteriously slow on a large ORDER BY is a strong candidate for "raise work_mem so the sort stays in memory" — a real, checkable operational lever, not just interview trivia.

MapReduce's shuffle phase. Each mapper sorts its own local output (phase 1); each reducer merges the sorted outputs it receives from every mapper before its reduce function runs (phase 2) — the same two-phase structure, with "chunk" replaced by "one mapper's partition" and the merge happening over the network instead of local disk. "Group by key at a scale no single machine holds" is fundamentally an external-sort problem.

Cost model

Cost	Why it dominates
Disk passes (O(n/B) block transfers per pass)	Each full read+write pass over the data, not comparisons, is what wall-clock time actually tracks
Merge fan-in limit	A real system can't hold unlimited file handles/heap entries open — bounds how many chunks merge per round, which sets the pass count

Not covered here

The in-memory sort used for each chunk — see the DSA roadmap's Sorting Algorithms topic. The min-heap merge itself is the same K-Way Merge pattern used for merging k sorted lists, with full complexity analysis and practice problems there.

Where this goes next

ACID & Isolation Levels moves from how bytes persist to what concurrent transactions are allowed to see.