External sorting

Phase 1 (run generation): read as much data as fits in memory, sort it with any internal sort, and write the sorted chunk to disk as a run. Phase 2 (merging): merge the runs, k at a time, into larger runs until a single sorted run remains.

Merging is sequential: each run is read front to back and the output is written front to back. Sequential access is what disks and SSDs do best, which is why merge sort and not quick sort is the external sort of choice.

A run is a sorted sequence stored on disk. With N records and memory for M records, simple run generation produces ⌈N / M⌉ runs of length M.

Replacement selection generates longer runs. It keeps a heap in memory; the smallest value greater than the last value written goes out next, and a new value that is too small is held for the next run. On random input the average run length is about 2M, which halves the number of runs.

To merge k runs, keep the current head of each run. Repeatedly output the smallest head and read the next element from that run. The animation finds the smallest head by scanning the k heads, which costs O(k) per element; the heap version below needs only O(log k).

With a min-heap of at most k heads, merging n records in total costs O(n log k). Choose k as large as the memory for one buffer per run allows, to reduce the number of passes.

1record Head(int value, int run) {}
2
3static void kWayMerge(List<Iterator<Integer>> runs, Consumer<Integer> out) {
4    PriorityQueue<Head> heap = new PriorityQueue<>(Comparator.comparingInt(Head::value));
5    for (int r = 0; r < runs.size(); r++) {
6        if (runs.get(r).hasNext()) heap.add(new Head(runs.get(r).next(), r));
7    }
8    while (!heap.isEmpty()) {
9        Head h = heap.poll();                     // smallest of the k heads: O(log k)
10        out.accept(h.value());
11        Iterator<Integer> run = runs.get(h.run());
12        if (run.hasNext()) heap.add(new Head(run.next(), h.run()));
13    }
14}

1public static int[] kWayMerge(int[][] runs) {
2    int k = runs.length, total = 0;
3    for (int[] r : runs) total += r.length;
4    int[] pos = new int[k];                // next unread index in each run
5    int[] out = new int[total];
6    for (int o = 0; o < total; o++) {
7        int best = -1;
8        for (int r = 0; r < k; r++) {
9            if (pos[r] < runs[r].length &&
10                (best == -1 || runs[r][pos[r]] < runs[best][pos[best]])) {
11                best = r;
12            }
13        }
14        out[o] = runs[best][pos[best]++];
15    }
16    return out;
17}

Reading a record from disk can be a million times slower than comparing two records in memory, so the cost model counts block transfers. Every pass reads the whole data set once and writes it once.

The number of passes is 1 (run generation) plus ⌈log_k(number of runs)⌉ merge passes. Example: a 100 GB file, 1 GB of memory, 100 runs. A 2-way merge needs ⌈log₂ 100⌉ = 7 merge passes. A 100-way merge, with 100 buffers of 10 MB each, needs a single merge pass.

Practical systems rarely write this themselves. Databases use external merge sort for ORDER BY and sort-merge joins, and MapReduce-style frameworks sort partitions then merge them. In Java you can use a file-backed approach: read chunks, sort them with Arrays.sort, write each to a temporary file, and merge with the heap code above.

Alternatives when the data has structure: distribution sorts partition by key range so each partition fits in memory, and radix-based approaches reduce passes for integer keys.