External merge sort

Deep dive

How it works

Parts:

• run generator — in-memory sorter that turns memory-sized chunks into sorted runs
• run files — sorted sequences on disk, written and read sequentially
• read buffers — one block (≥ 1 MB) per run, refilled ahead of the merge
• merger — heap or loser tree holding each run's current head
• output writer — buffered sequential write of the merged stream

Operations:

1. Run generation: fill memory with records, sort (in-memory sort of keys or (key, pointer) pairs), write sequentially. Replacement selection (a heap that keeps emitting while reading) produces runs averaging 2× memory on random input and one run on sorted input, at the cost of heap-speed sorting.
2. Merge: open k runs, each with a read buffer; a min-heap (or loser tree) holds each run's current head; pop min, write, refill from that run.
3. If runs > k, merge in groups of k into longer runs, repeat (multi-pass).
4. Double-buffer: prefetch the next block of each run asynchronously and write output asynchronously so CPU and I/O overlap.

input (1 TB) ──read 1 GB──► sort ──► run_0 ... run_999        pass 0: read 1 TB, write 1 TB
run_0..999 ──1 MB buffer each──► heap(1000) ──► output        pass 1: read 1 TB, write 1 TB

Code

Sorts a file of little-endian u64 keys with bounded memory: mem_items × 8 bytes for runs, fan_in × 1 MB for merging.

use std::cmp::Reverse;
use std::collections::{binary_heap::PeekMut, BinaryHeap};
use std::fs::{self, File};
use std::io::{self, BufReader, BufWriter, Read, Write};
use std::path::{Path, PathBuf};

const IO_BUF: usize = 1 << 20; // 1 MB per stream keeps merge reads sequential

fn read_u64(r: &mut impl Read) -> io::Result<Option<u64>> {
    let mut b = [0u8; 8];
    match r.read_exact(&mut b) {
        Ok(()) => Ok(Some(u64::from_le_bytes(b))),
        Err(e) if e.kind() == io::ErrorKind::UnexpectedEof => Ok(None),
        Err(e) => Err(e),
    }
}

fn make_runs(input: &Path, tmp: &Path, mem_items: usize) -> io::Result<Vec<PathBuf>> {
    let mut r = BufReader::with_capacity(IO_BUF, File::open(input)?);
    let (mut runs, mut buf) = (Vec::new(), Vec::with_capacity(mem_items));
    loop {
        buf.clear();
        while buf.len() < mem_items {
            match read_u64(&mut r)? { Some(x) => buf.push(x), None => break }
        }
        if buf.is_empty() { return Ok(runs); }
        buf.sort_unstable();
        let path = tmp.join(format!("run-{}.bin", runs.len()));
        let mut w = BufWriter::with_capacity(IO_BUF, File::create(&path)?);
        for x in &buf { w.write_all(&x.to_le_bytes())?; }
        w.flush()?; // temp files need no fsync
        runs.push(path);
        if buf.len() < mem_items { return Ok(runs); }
    }
}

fn merge(runs: &[PathBuf], out: &Path) -> io::Result<()> {
    let mut readers = runs.iter()
        .map(|p| Ok(BufReader::with_capacity(IO_BUF, File::open(p)?)))
        .collect::<io::Result<Vec<_>>>()?;
    let mut heap = BinaryHeap::with_capacity(runs.len());
    for (i, r) in readers.iter_mut().enumerate() {
        if let Some(x) = read_u64(r)? { heap.push(Reverse((x, i))); }
    }
    let mut w = BufWriter::with_capacity(IO_BUF, File::create(out)?);
    while let Some(mut top) = heap.peek_mut() {
        let Reverse((x, i)) = *top;
        w.write_all(&x.to_le_bytes())?;
        match read_u64(&mut readers[i])? {
            Some(y) => *top = Reverse((y, i)), // replace-top: one sift-down instead of pop + push
            None => { PeekMut::pop(top); }
        }
    }
    w.flush()
}

pub fn external_sort(input: &Path, output: &Path, tmp: &Path, mem_items: usize, fan_in: usize) -> io::Result<()> {
    let mut runs = make_runs(input, tmp, mem_items)?;
    let mut pass = 0;
    while runs.len() > fan_in { // multi-pass only when runs exceed the fan-in
        let mut next = Vec::new();
        for (j, group) in runs.chunks(fan_in).enumerate() {
            let p = tmp.join(format!("pass{pass}-{j}.bin"));
            merge(group, &p)?;
            next.push(p);
        }
        for p in &runs { fs::remove_file(p)?; }
        (runs, pass) = (next, pass + 1);
    }
    merge(&runs, output)?;
    for p in &runs { fs::remove_file(p)?; }
    Ok(())
}

Complexity and constants

• Fan-in k ≈ (merge memory) / (buffer per run). 4 GB and 4 MB buffers → k ≈ 1,000; one merge pass sorts up to k × run size = 1,000 × 4 GB = 4 TB.
• Device time for 1 TB at ~4 × data size of I/O: NVMe at 3-7 GB/s → order of 10-25 minutes if CPU keeps up; one HDD at ~200 MB/s → order of 5-6 hours. Striping across disks scales linearly.
• CPU: run generation is an in-memory sort (order of 10 ns/key for 8-byte keys); merging costs log2(k) comparisons per record plus copying; a loser tree does exactly ⌈log2 k⌉ comparisons with fewer branches than a binary heap.
• Buffer size trade-off: HDD seeks (~5-10 ms) need buffers of several MB to amortize; NVMe is fine with 256 KB-1 MB but benefits from queue depth (async reads).

Efficiency

• Cost: total I/O is about 4 × data size for the usual two passes (read and write in run generation, read and write in the merge). 1 TB on NVMe at 3-7 GB/s is order of 10-25 minutes, on one HDD at about 200 MB/s order of 5-6 hours (both from the figures above). CPU: order of 10 ns/key to sort runs, plus ⌈log2 k⌉ comparisons per record when merging. Memory: the run size M plus k read buffers. Bound: I/O on HDD, often CPU on NVMe.
• Levers:
  • buffers of ≥ 1 MB per run — merge stays sequential; tiny buffers run 10-100× slower on HDD (order of) — HDD and network disks
  • fan-in k = M/B — keeps it to one merge pass, 4 GB and 4 MB buffers sort up to 4 TB — data well above RAM
  • run compression (LZ4/zstd -1) — roughly halves I/O (order of) — I/O-bound sorts
  • loser tree instead of binary heap — exactly ⌈log2 k⌉ comparisons, fewer branches — large k
  • striping and parallel run generation — scales with disks and cores — multi-disk or multi-core hosts
• Naive → standard → state of the art:
  • binary merges, log2(n/M) passes · 2n I/O per pass
  • run generation plus one k-way merge, heap · about 4 × data I/O
  • normalized keys, radix-sorted runs, async I/O, compressed runs, parallel splitter-based merge · bound by device bandwidth (Nyberg et al. 1994)

Implementation notes

• Sort keys, not records: in memory, sort (normalized key prefix, pointer) pairs; normalized keys are memcmp-able byte strings (fixed-width prefix of the key with sign bits flipped), which also enables radix sort.
• Compress runs with LZ4/zstd -1 when I/O-bound: halves I/O at modest CPU cost.
• Async I/O / double buffering: read the next block of each run while merging the current one (io_uring, a reader thread per device, or posix_fadvise(SEQUENTIAL)).
• Parallelism: generate runs on all cores; parallelize the final merge by splitting the key range with splitters sampled from runs, each thread merging one key range.
• Avoid the page cache for huge sorts (O_DIRECT with aligned buffers): otherwise runs evict useful cache and get double-buffered.
• Early aggregation / dedup in run generation (combine equal keys) shrinks runs for GROUP BY and DISTINCT.
• Top-k with spill: keep only runs' first k elements when there is a LIMIT.

Pitfalls

• Too many open files: k runs need k descriptors; raise ulimit -n or bound the fan-in.
• Tiny read buffers (the default 8 KB of BufReader): the merge turns into random I/O and runs 10-100× slower on HDDs.
• Temp space: you need about 1× input size free (2× with multi-pass if old runs are not deleted promptly).
• Unstable merge: ties should break by run index (as the (x, i) tuple does) if the order of equal keys matters.
• Memory accounting by record count instead of bytes with variable-size records: OOM on large values.

Variants and alternatives

In production

Databases: PostgreSQL tuplesort, DuckDB and ClickHouse external ORDER BY, RocksDB/LevelDB compaction. Data processing: Apache Spark (UnsafeExternalSorter spills), Hadoop MapReduce shuffle (map-side spills merged with io.sort.factor), GNU sort (temp-file runs, merges 16 at a time by default). Genomics: samtools sort writes temporary sorted files when the data exceeds -m memory and merges them. Benchmarks: the Sort Benchmark (sortbenchmark.org) entries.

Implementations

Sources

• D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., 1998 (section 5.4).
• A. Aggarwal, J. S. Vitter, The Input/Output Complexity of Sorting and Related Problems, CACM, 1988. paper
• G. Graefe, Implementing Sorting in Database Systems, ACM Computing Surveys, 2006. paper
• C. Nyberg, T. Barclay, Z. Cvetanovic, J. Gray, D. Lomet, AlphaSort: A RISC Machine Sort, SIGMOD, 1994. paper
• GNU coreutils manual, sort invocation (temporary files, --batch-size). docs
• HTSlib, samtools sort. docs