Every sorting algorithm covered so far assumes the data fits in RAM. External Sort is the algorithm that runs when it does not. Sorting a 1 TB log file on a machine with 16 GB of memory, or merging the per-shard output of a distributed MapReduce job, or processing a CSV that is too large for pandas to load, all reduce to External Sort.

The algorithm is conceptually simple and has been the standard answer since the 1950s, when "external" meant "magnetic tape." The two phases:

This chapter covers the algorithm, the heap-based merge that makes it efficient, the I/O complexity, the tuning knobs that matter in practice (chunk size, fan-in), and the systems that ship External Sort variants internally.

A 1 TB file on a machine with 16 GB RAM cannot be loaded with one read() call. Even attempting it triggers paging, then thrashing, then process termination. The OS will swap pages to disk arbitrarily, which is the worst possible access pattern for sorting (every comparison potentially causes two page faults).

External Sort sidesteps this by explicitly choosing what to keep in memory. At any time, only a controlled amount of data is resident: a single chunk during phase 1, and k blocks (one per merge input) during phase 2. This keeps total memory use bounded and predictable.

The other key property: External Sort uses sequential I/O throughout. Reading and writing in long streams is one to two orders of magnitude faster than random I/O, on both spinning disks (seek time is the bottleneck) and SSDs (large sequential reads avoid amplification). Merge Sort is the only standard in-memory sort whose data-access pattern is sequential-friendly, which is why every External Sort is built on it.

Choose a chunk size M based on available memory. A common rule of thumb is to use half of the available RAM, leaving room for the OS, the sort buffers, and a margin of safety.

For each chunk:

After phase 1, the input has been replaced with ceil(n / M) sorted files. Each is at most M bytes; the last may be smaller. The set of files together contains the same records as the input, sorted within each file but unsorted across files.

Phase 1 cost in I/O terms: each record is read once and written once. For an input of n records, phase 1 does 2n I/O operations.

Phase 2 combines the k = ceil(n / M) sorted runs into a single sorted output. The naive approach is to merge them two at a time, like a binary merge: merge run 0 with run 1 to produce run 0', merge run 0' with run 2, and so on. Each merge passes every record through I/O once, so a binary merge of k runs costs k * n total I/O. For k = 1000, that is 1000 * n reads and writes, far too much for a disk-bound workload.

The better approach is a multi-way merge: open all k runs at once and merge them in a single pass using a min-heap. Each record is read once and written once, for a total of 2n I/O in phase 2.

The Min-Heap Merge

To produce the next output record, look at the smallest current record across all k runs. The candidates are the head of each run. A linear scan of k heads costs O(k) per output record, for O(nk) total comparisons. A min-heap reduces this to O(log k) per output record, for O(n log k) total.

The heap stores k entries, one per run, where each entry is (value, runIndex). The heap is keyed by value. Loop:

The heap stays at size <= k throughout.

A complete production External Sort handles temp file management, buffered I/O, and error recovery. The simulation below ignores those concerns and operates on in-memory lists in place of files, which keeps the algorithmic core visible without disk-level plumbing.

Python's standard library has heapq.merge, which already implements an efficient k-way merge over sorted iterables. In production code, that builtin is preferred over a hand-written heap loop:

The simulation captures the algorithm at the level that matters. A real implementation replaces the lists with file handles, the chunk extraction with a read(chunkSize) from the input file, and the output add with a buffered write to the final output file. The skeleton stays identical.

A binary merge with log2(k) levels would also produce a sorted output, but at much higher I/O cost.

For k = 1000:

The savings are large on disk-bound workloads. The cost: phase 2 needs k file handles open simultaneously, plus a buffer per handle. For k = 10000 and 1 MB buffers, that is 10 GB of buffer memory. Real systems trade off k against per-handle buffer size to stay within available memory.

If k is too large to merge in a single pass (because memory cannot hold one buffer per run), do a two-phase merge: merge groups of k' runs into intermediate runs, then merge the intermediate runs. This brings the total I/O passes to log_{k'}(k) + 1, still far below binary merge for any reasonable k'.

External Sort is analyzed in terms of I/O operations, not CPU operations, because disk I/O is the dominant cost. The standard model is the External Memory Model by Aggarwal and Vitter: data is moved in blocks of size B, and the algorithm has M bytes of memory.

For an input of n records:

For very large k (one pass of merging is not enough because the heap would not fit in memory), the I/O cost becomes O((n / B) * log_{M/B}(n / B)), which is the classic external sort lower bound.

Compared to in-memory sorts where the dominant cost is CPU comparisons (O(n log n)), External Sort's dominant cost is I/O bandwidth. Optimization focuses on minimizing passes over the data, not minimizing comparisons.

Replacement selection is an optimization from the tape-sort era that still helps on modern systems. Instead of fixed-size chunks, phase 1 uses it to produce runs that are on average twice as long as the chunk size.

The technique: maintain a min-heap of size M. For each output record:

The deferred heap is what extends runs. On uniformly random input, replacement selection produces runs averaging 2M long instead of M.

The trade-off: replacement selection produces fewer but longer runs, which reduces the merge fan-in needed in phase 2. For massive datasets where one pass of merging would otherwise be impossible, replacement selection can halve the number of phases. For inputs where the simpler chunked sort works fine, the added complexity of replacement selection is rarely worth it.

External Sort is the foundation of several systems infrastructure components:

The GNU sort example is the most accessible. Running sort huge_file.csv > sorted.csv on a file larger than RAM transparently does external sort, with temp files in $TMPDIR. The default chunk size is conservative (SORT_SIZE env var); raising it toward available memory reduces the number of runs and merge passes, which speeds up the sort.

Three parameters dominate the performance of an External Sort implementation.

Chunk size (M). Bigger chunks mean fewer runs and a smaller fan-in in phase 2. The limit is available memory. Use as much memory as you can without paging.

Fan-in (k). Higher fan-in means fewer merge passes. The limit is memory per merge buffer: k * buffer_size must fit in memory. For SSDs, smaller buffers per stream work fine (random read penalty is mild). For HDDs, larger buffers per stream avoid seek thrashing.

Buffered I/O. Reading one record at a time from a file issues a separate syscall and disk access per record, which is slow. Use buffered reads with at least a 4 KB block, ideally 64 KB or larger. The buffer amortizes the per-syscall and per-disk-seek cost across many records.

A typical production tuning for a 1 TB sort on a 64 GB machine:

External Sort fits the "single machine, data larger than memory" regime. Once data is distributed across machines (because it does not even fit on one disk), the algorithm extends to TeraSort and distributed merge sort, where phase 1 happens on each node and phase 2 is a coordinated network merge. The principles stay the same; only the I/O substrate changes.

Forgetting buffered I/O. Reading and writing one record at a time bypasses the disk's natural sequential-access advantage. Always wrap file handles with buffered readers and writers.

Letting k get too large. Opening 100k temp files and trying to merge them all in one pass exhausts file descriptors and memory. Cap the fan-in and merge in multiple phases when necessary.

Using random I/O during merge. The merge phase should read from each run sequentially. Random access to the middle of a run defeats the entire point of External Sort.

Ignoring temp file location. Temp files default to /tmp on Linux, which is often a small in-memory tmpfs. Sorting a 1 TB file with tmpfs as temp storage runs out of space immediately. Use --temporary-directory (for GNU sort) or the equivalent option to redirect temp files to a real disk.

Not handling tie-breaking for stability. Like in-memory sorts, External Sort can be made stable by using strict < comparisons in the merge step. Production sorts often need this when ordering by a non-primary key.

Confusing CPU bound vs I/O bound. Optimizing the in-memory sort algorithm in phase 1 is rarely the bottleneck. The bottleneck is disk bandwidth, so the right place to optimize is buffer sizes, fan-in, and temp file placement.

The B in the I/O formulas is the disk block size, and M is the available memory. For typical values (B = 4 KB, M = 16 GB), the log_{M/B} term is so small that two phases is enough for any input up to many terabytes.