External Sorting Explained

The cost model changes completely. In RAM, a random access costs about 100 nanoseconds. On an SSD it is roughly 100 microseconds — a thousand times more. On a spinning disk, around 10 milliseconds — a hundred thousand times more. So the quantity to minimise is no longer operations but I/O, and specifically random I/O.

Storage has a second property that decides everything: sequential access is dramatically faster than random access. Reading a 1 GB file front to back might sustain 500 MB/s on an SSD; reading the same gigabyte in scattered 4 KB chunks can be an order of magnitude slower, and on a spinning disk it is far worse because every seek is mechanical.

Now the ranking inverts. Quick Sort's partition walks two indices toward each other across the whole range — fine in cache, but on a file it means constant seeking. Merge Sort reads its inputs strictly front to back and writes its output front to back. Everything it does is sequential. The algorithm that loses in RAM because of cache behaviour wins on disk for the very same structural reason.

External merge sort has exactly two phases. The first turns one unsorted file into many sorted ones.

Read as much of the input as comfortably fits in memory — call it M — sort that chunk with any good in-memory algorithm (Quick Sort is fine here; this part is in RAM), and write the sorted chunk out to a temporary file. That file is called a run. Repeat until the input is exhausted.

With 500 GB of input and 4 GB usable for sorting, you finish with about 125 sorted runs of 4 GB each. Cost so far: one sequential read of the whole input and one sequential write of the whole input.

A refinement worth knowing: replacement selection can produce runs roughly twice as long as memory. Instead of filling memory, sorting and dumping, you keep a heap in memory and continuously emit the smallest value that is still ≥ the last one written, refilling from the input as you go. Because incoming values are often larger than the last emitted one, runs average about 2M in length. Fewer, longer runs mean less merging work later.

Now merge the runs. The key insight is that merging sorted sequences needs only one element from each in memory at a time, so you can merge a hundred 4 GB runs while holding only a few megabytes.

Keep a small read buffer per run and a min-heap holding the current front element of each. Repeatedly pop the smallest from the heap, write it to the output, and push the next element from whichever run it came from. Each pop-and-refill is O(log k) for k runs, and every read and write is sequential.

procedure kWayMerge(runs, output):
  heap = empty min-heap                  // holds (value, runIndex)
  for each run r in runs:
    heap.push((read next value from r), r)

  while heap not empty:
    (value, r) = heap.popMin()
    write value to output                // sequential write
    if r has more values:
      heap.push((read next value from r), r)

If there are more runs than you can buffer at once, merge in passes: combine the runs in groups of k, producing fewer and longer runs, and repeat. The number of passes is ⌈log_k(number of runs)⌉ — which is why a larger k is valuable. With 125 runs and k = 125 you merge in a single pass; with k = 10 you need three passes, and each pass reads and writes the entire dataset again.

Total I/O for a single-pass merge is two sequential reads and two sequential writes of the whole dataset. For 500 GB at 500 MB/s that is roughly half an hour of pure I/O — entirely reasonable, and the crucial point is that it never required 500 GB of RAM.

The one real tuning decision is k, the number of runs merged simultaneously, and it is a genuine trade-off.

A larger k means fewer passes over the data, which is the dominant cost. But each of the k runs needs its own read buffer, and with memory M the buffer per run is about M/k. Push k too high and buffers shrink until reads stop being usefully sequential — at which point you have traded fewer passes for slower reads and made things worse.

In practice implementations aim for buffers large enough to keep reads sequential (often a few hundred KB to a few MB each) and set k from whatever memory remains. This is precisely what a database is doing when its sort spills: PostgreSQL's work_mem, for instance, decides both how large the initial runs are and how many can be merged at once, which is why raising it can turn a three-pass sort into a one-pass sort and produce a startling speedup on a big ORDER BY.

External sorting is invisible infrastructure, and it is running underneath a lot of ordinary work.

Databases. An ORDER BY that cannot be answered from an index sorts in memory if it fits and spills to an external merge sort if it does not. The same machinery powers sort-merge joins, GROUP BY on large result sets, and index builds. If you have ever seen a query plan mention an "external merge" or temporary files, this is it.

Big data frameworks. The shuffle phase of MapReduce is a distributed external sort: mappers write sorted spill files, and reducers merge them. Spark's sort-based shuffle does the same, and both are why "sort" appears in job stages you never asked to sort.

LSM-tree storage engines. Cassandra, RocksDB, LevelDB and friends write sorted immutable files and periodically merge them into larger sorted files. Compaction is a k-way merge of sorted runs, which is exactly phase 2 above running forever in the background.

Command-line sort. GNU sort handles files far larger than memory by doing precisely this, writing temporary runs into /tmp and merging them. sort -S tunes the memory budget, and it moves the pass count the same way work_mem does.

"How would you sort 100 GB of data on a machine with 4 GB of RAM?" is a standard system-design question, and it has a clean answer. State the two phases: split the input into chunks that fit in memory, sort each with an in-memory algorithm and write it out as a sorted run; then k-way merge the runs using a min-heap and a small buffer per run.

Then add the reasoning that shows you understand why, which is what actually distinguishes the answer. Merging is the right shape because it reads and writes sequentially, and sequential I/O is orders of magnitude faster than random I/O. Merging needs only one element per run resident, so memory bounds the fan-in, not the data size. The tuning knob is k, trading pass count against buffer size. And this is not a hypothetical construction — it is what every database does when a sort exceeds its memory budget.

If you want to build the intuition for the merge step itself first, watch Merge Sort run in the visualiser. The merge you are watching is the same operation; external sorting just changes where the two sorted sequences are stored.