C & C++

External sort explained: sorting data that does not fit in memory

Himanshu Sharma · 25 January 2023 · 10 min read

Every sorting algorithm you meet first (bubble sort, quicksort, merge sort) assumes the data sits in the computer's memory, where any element is available instantly. What if it does not? A log file with billions of lines, a database table of 500 GB, or a list of a hundred million records on a laptop with 8 GB of RAM cannot be loaded and sorted in one go. External sorting is the family of techniques for sorting data that is bigger than main memory, keeping most of it on disk. The classic method is external merge sort: sort pieces that fit in memory, then merge the pieces. This post explains it step by step, shows a worked example, measures a real implementation, and explains where it is used in practice.

Why not just use ordinary sorting?

An internal sort works on data in RAM. Two things go wrong when the data is larger than RAM:

It does not fit. Loading the file fails or the program is killed for using too much memory.
Virtual memory makes it crawl. The operating system can pretend there is more memory by swapping parts to disk, but ordinary sorting jumps around the data randomly, causing constant swapping ("thrashing"), and it can be thousands of times slower.

The right design principle is that disk is accessed best sequentially. Reading or writing a long stretch of a file in order is fast; jumping between random positions is slow (especially on spinning disks). External sorting is built to read and write in long sequential streams. It pays attention to the number of times the data is read from disk and written back (the I/O cost), not to the number of comparisons.

The idea in two phases

Phase 1: create sorted runs. Read as much data as fits in memory (a chunk), sort it with any fast internal sort, and write it to a temporary file called a run. Repeat until all the input is consumed. Now the data is a set of sorted runs on disk.

Phase 2: merge the runs. Open all the runs at once and repeatedly pick the smallest of the current first elements, writing it to the output. Because each run is already sorted, the smallest remaining element overall must be at the front of one of the runs. This is a k-way merge. Only one element (or a small buffer) per run needs to be in memory at a time.

A small worked example

Suppose we have 12 numbers, but memory can only hold 4 at a time:

input:  42 7 19 88 | 3 56 24 91 | 15 60 33 8

Phase 1 reads four numbers at a time, sorts them, and writes each run. I ran this:

run 1: [42, 7, 19, 88] -> sorted [7, 19, 42, 88]
run 2: [3, 56, 24, 91] -> sorted [3, 24, 56, 91]
run 3: [15, 60, 33, 8] -> sorted [8, 15, 33, 60]

Phase 2 merges the three runs. Look at the front of each run: 7, 3 and 8. The smallest is 3 (run 2), so write 3 and advance run 2 to 24. Now the fronts are 7, 24, 8, so write 7. Then fronts 19, 24, 8: write 8. Then 19, 24, 15: write 15. And so on. The result:

merged: [3, 7, 8, 15, 19, 24, 33, 42, 56, 60, 88, 91]

which equals the fully sorted input. The merge never needs more than three numbers in memory (one per run), however long the runs are. A min-heap (priority queue) holding the front element of each run finds the smallest in O(log k) time, where k is the number of runs.

A complete implementation in Python

Python's standard library does the heavy lifting: list.sort for the chunks and heapq.merge for the k-way merge, which works lazily and reads one item at a time from each iterator.

import heapq
import os
import random
import tempfile

CHUNK_SIZE = 100_000            # how many numbers fit in memory at once


def write_run(numbers, tmpdir):
    """Sort one chunk in memory and write it to a temporary 'run' file."""
    numbers.sort()
    fd, path = tempfile.mkstemp(dir=tmpdir, suffix=".run")
    with os.fdopen(fd, "w") as f:
        f.writelines(f"{n}\n" for n in numbers)
    return path


def split_into_runs(src, tmpdir):
    runs, chunk = [], []
    with open(src) as f:
        for line in f:
            chunk.append(int(line))
            if len(chunk) == CHUNK_SIZE:
                runs.append(write_run(chunk, tmpdir))
                chunk = []
    if chunk:
        runs.append(write_run(chunk, tmpdir))
    return runs


def merge_runs(runs, dest):
    files = [open(p) for p in runs]
    try:
        streams = [(int(line) for line in f) for f in files]      # lazy: one line at a time
        with open(dest, "w") as out:
            for n in heapq.merge(*streams):
                out.write(f"{n}\n")
    finally:
        for f in files:
            f.close()


def external_sort(src, dest):
    with tempfile.TemporaryDirectory() as tmpdir:
        runs = split_into_runs(src, tmpdir)
        merge_runs(runs, dest)
        return len(runs)

How it works: split_into_runs reads the input line by line (never the whole file), collects CHUNK_SIZE numbers, and hands them to write_run, which sorts them and saves a temporary file. merge_runs opens every run, wraps each in a generator that turns lines into integers, and lets heapq.merge combine them in order, writing the output line by line. The temporary directory and its files are deleted automatically.

Testing it

I generated a file of one million random integers (about 10 MB) with a fixed random seed and sorted it:

if __name__ == "__main__":
    random.seed(42)
    with open("big.txt", "w") as f:
        f.writelines(f"{random.randint(0, 10**9)}\n" for _ in range(1_000_000))
    runs = external_sort("big.txt", "sorted.txt")
    print("runs created:", runs)

    previous, count = -1, 0
    with open("sorted.txt") as f:
        for line in f:
            n = int(line)
            assert n >= previous, "not sorted!"
            previous, count = n, count + 1
    print("lines:", count, "sorted:", True)

runs created: 10
lines: 1000000 sorted: True

Ten runs of 100,000 numbers each were created and merged, and the checker confirmed that all 1,000,000 lines were in non-decreasing order. I also sorted the same file the ordinary way (read everything into a list, sort, write) and compared the output files: they were identical. The resource use was different:

Method	Time	Peak memory
Ordinary in-memory sort	about 0.46 s	about 55 MB
External sort (10 runs of 100,000)	about 0.93 s	about 17 MB

(These are single timings from one laptop and one Python process, which already uses around 10 MB, so only the pattern matters.) The external sort used about a third of the memory and took about twice as long, which is the trade you accept: it is slower than sorting in memory when memory is enough, but it keeps working when memory is not. Make the file 100 times bigger, and the in-memory version stops working at all, while the external one still needs about the same 17 MB; only its runtime grows.

How much work is it? Passes and I/O cost

Let N be the number of records in the file, M the number that fit in memory, and k the number of runs you can merge at once (limited by how many files and buffers you can hold open).

Phase 1 creates about N / M runs. Each record is read once and written once.
Phase 2, if N / M ≤ k, merges everything in one pass: each record is read once more and written once more.
If there are more runs than k, you merge in several passes. The number of merge passes is ⌈log base k of (N / M)⌉.

For our 1,000,000 numbers, M = 100,000 and N / M = 10 runs, so one merge pass was enough. In a typical real system, M is gigabytes and k is in the hundreds or thousands, so even a data set of hundreds of times the memory size can be sorted in just two passes over the data: one to make runs and one to merge. The total I/O is roughly 4 × (data size): read, write runs, read runs, write output.

The CPU cost of the in-memory sorts is O(N log M) and of the merging O(N log k). Disk speed usually dominates, which is why the designs concentrate on sequential access and large buffers (reading a block of many records per disk request, not one record).

Improvements used in practice

Replacement selection: instead of sorting fixed chunks, keep a heap of M records and keep emitting the smallest that is not smaller than the last one written; on random input this makes runs about twice as long as memory (about 2M), so there are half as many runs. On already partly sorted input, the runs can be far longer.
Multi-way merging with buffers: read and write in big blocks; use a double buffer to read the next block while the CPU works on the current one.
Multiple disks or threads: run the sorting of chunks in parallel; spread runs over several disks.
Compression and fixed-width keys: sort a compact key plus a pointer to the full record, not the whole record.
Polyphase merge: an older scheme for tape drives that merges unevenly to reduce the number of passes and the number of devices. It is mostly of historical and exam interest now.

Where it is used

Databases: ORDER BY, GROUP BY, DISTINCT and merge joins on big tables spill to disk when they exceed the sort buffer. In MySQL, Using filesort in an EXPLAIN plan can mean exactly this, and a good index lets the database skip the sort entirely.
Unix sort: the command-line sort tool uses temporary files and merges them, so sort hugefile.txt works on files larger than memory.
Big data systems: Hadoop's MapReduce and Spark sort and merge shuffled data in the same way, across many machines.
Search engines and log analysis: building indexes, de-duplicating records and ordering events by time.
Data science: sorting datasets too large for one machine's memory.

Related ideas

Internal merge sort is the in-memory algorithm of which this is the disk-friendly cousin; both use "split, sort, merge". Understanding how merging two sorted lists works is the key skill.
Top-k problems (the 10 largest of a billion numbers) do not need a full sort: a heap of size k scans the data once.
Counting and bucketing (radix or distribution sort) can beat comparison sorting when keys are small integers.

Common questions

Is external sorting a particular algorithm? No, it is a technique. The standard version is external merge sort.
Is it stable? It can be, if the merge prefers the earlier run when keys are equal, and the chunk sorting is stable (Python's sort is).
What is the worst case? About the same as the best: every record is read and written a fixed number of times, so the runtime is predictable.
When should I not use it? When the data fits in memory comfortably; an ordinary sort is simpler and faster, as the timings show.

Practice

Change CHUNK_SIZE to 10,000, 100,000 and 500,000 and note the number of runs, the time and the peak memory. Add a command-line argument for the key (sort lines of a CSV by its second column). Add a limit on how many runs are merged at once, and do the merge in several passes when there are more. Finally, try the same job in C with qsort for the chunks and a manual merge.

Next steps

Sorting is one chapter of the broader subject of data structures and algorithms. Read about lists and sorting in Python, check how a database speeds up sorting with an index, see why measuring beats guessing in SQL performance optimisation, and build the basics first in fundamentals of technology, which explains the difference between RAM and storage that makes external sorting necessary.