External Sorting

Sorting data too large for memory by merging sorted runs read from and written to external storage.

When data exceeds RAM

External sorting orders a dataset that does not fit in main memory by minimizing the number of slow disk passes. The dominant cost is I/O, not comparisons, so the goal is to read and write each record as few times as possible. The classic method is external merge sort.

Run generation and merging

In the first pass, read as much data as fits in memory, sort it (a run), and write it back. Then repeatedly merge groups of runs: a k-way merge reads the front of k sorted runs, uses a min-heap or loser tree to emit the smallest, and refills from the run it came from. Each merge pass reduces the run count by a factor of k until a single sorted file remains.

k-way merge core

python

import heapq

def k_way_merge(run_iters):
    heap = []
    for idx, it in enumerate(run_iters):
        first = next(it, None)
        if first is not None:
            heapq.heappush(heap, (first, idx))
    while heap:
        val, idx = heapq.heappop(heap)
        yield val
        nxt = next(run_iters[idx], None)
        if nxt is not None:
            heapq.heappush(heap, (nxt, idx))

Tuning I/O

• Larger merge fan-in k means fewer passes but more memory for buffers.
• Replacement selection produces runs about twice the memory size, cutting the number of initial runs.
• Double buffering overlaps computation with reads and writes.
• The number of passes is roughly log_k(number of initial runs), so k is the main lever.

Where it is used

Databases sort large query results and build indexes with external merge sort; big-data frameworks shuffle and sort partitions the same way. The same run-and-merge structure underlies the disk-friendly design of B+ trees and log-structured merge trees.