External Merge Sort: Sorting Data Bigger Than RAM

WHY IT EXISTS Standard sorting algorithms like Quicksort assume the entire dataset can fit into main memory (RAM). When data is too massive for RAM, it must live on slower external storage like a disk. External sorting was invented to handle these situations, working with data on disk without trying to load it all at once.

THE MENTAL MODEL Imagine you have to sort a million library books with only a small cart. You can't lay them all out. Instead, you'd take a cart-full, sort it, and stack the sorted books neatly. You'd repeat this for all the books, creating many sorted stacks. Finally, you'd merge all your sorted stacks into one final, perfectly sorted collection. External merge sort does exactly this with data chunks and disk files.

HOW IT WORKS The algorithm has two main phases.

First, the SORT PHASE: The algorithm reads a chunk of the large file that can fit into RAM. It sorts this chunk using a fast in-memory algorithm and writes the sorted chunk, called a 'run', to a temporary file on disk. This process repeats until the entire input file has been converted into a set of sorted runs.

Second, the MERGE PHASE: The algorithm performs a multiway merge on all the sorted runs. It opens all the run files, reads a small piece from the beginning of each into memory buffers, and uses a min-heap to efficiently find the overall smallest element among them. This element is written to the final output file, and the next element from its source run is pulled into the merge process. This continues until all runs are merged into one single, sorted output file.

WHEN TO USE IT Use external merge sort when your dataset is significantly larger than your available RAM. It is a foundational algorithm in database systems for creating indexes on large tables and in large-scale data processing jobs that require sorting massive files, such as terabytes of logs.

WHEN NOT TO USE IT If your dataset fits comfortably in memory, do not use external sort. The overhead of reading and writing to disk makes it dramatically slower than a standard in-memory sort. For a dataset that fits in RAM, an algorithm like Timsort (Python's default) or Introsort (C++'s default) will be far more efficient.

ONE CANONICAL EXAMPLE Sorting a 100 GB log file on a machine with 16 GB of RAM. The system might read 8 GB chunks of the file into memory, sort them, and write them out as 13 sorted runs (100 GB / 8 GB ≈ 13). It would then perform a 13-way merge, reading from the 13 temporary files and writing to a final 100 GB sorted output file, using only a fraction of RAM for buffers during the merge.