11 External-Memory Sorting

Sorting is a core primitive across domains—from geometric algorithms and robotics to databases and bioinformatics—and many problems (like deduplication and element distinctness) reduce to or are accelerated by sorting. When datasets are far larger than RAM, the challenge is to design algorithms that minimize slow disk I/O, measured in block transfers. In the external-memory model, N is the number of records, M is main-memory size, and B is the block size; the overarching strategy is to stream data sequentially, form runs that fit in memory, and combine them with as few full-data passes as possible.

A direct external adaptation of mergesort first makes initial sorted runs of size about M in one sequential pass, then repeatedly merges them. Doing this naively in 2-way fashion takes about (N/B)·log₂(N/B) I/Os, because each merge level requires a full sweep. The key improvement is multi-way merging: keep one buffer block per run and an output buffer, and use a small in-memory heap to pick the next smallest item, allowing up to M/B runs to be merged at once. This M/B-way mergesort reduces the number of passes to log_{M/B}(N/B), achieving an I/O complexity of Θ((N/B)·log_{M/B}(N/B)). The change in logarithm base is substantial here because M and B are parameters, not constants, often yielding order-of-magnitude speedups.

Quicksort can be externalized too: a 2-way version scans the file once per level, partitioning around a pivot with two buffer blocks; when partitions fit in memory, they are sorted internally. To match mergesort’s I/O optimality, a multi-way version finds about M/B “good-enough” pivots in linear I/O by sorting chunks, sampling representatives, and selecting multiple approximate medians, then partitions into O(M/B) buckets in one pass using O(M/B) buffers. This yields the same Θ((N/B)·log_{M/B}(N/B)) I/O bound. Notably, unlike in RAM where balanced search trees equate the per-element costs of searching and sorting, in external memory sorting per element is asymptotically cheaper than B-tree inserts, highlighting the advantage of batching. A matching lower bound—derived by counting how many candidate orderings a single block transfer can eliminate given B-sized blocks and M-sized memory—proves that Θ((N/B)·log_{M/B}(N/B)) I/Os is optimal, making M/B-way mergesort (and multi-way quicksort) asymptotically optimal for external-memory sorting.

: Robot motion planning algorithms often involve computing convex hulls of the nearby objects.

: In bioinformatics, genomes are often ordered according to various criteria. In this particular case, we are ordering genomes by the number of times sequences X and Y have occurred. The importance of sequence X’s presence is valued as twice as that of sequence Y’s presence.

2-way mergesort adapted to external memory. In the first run, elements are processed in batches of size , where each batch of size is sorted. This is our “base case” for external-memory mergesort (internal memory mergesort ordinarily begins from lists of size 1). Then one by one, pairs of lists of size are processed and merged into lists of size , then , and so on. Eventually we arrive at the final list of size .

: Merging sorted lists in external memory. Each list has one representative buffer block residing in memory at all times. The minimum of each block is initially inserted into a heap, from where minima are repeatedly extracted. Every time an element is extracted from the heap, the next element in line from the same block where the minimum came from gets inserted into the heap. When we run out of elements of one particular block, we bring in the next block of the same list.

: In -way mergesort, we begin by creating in one run sorted lists of size . Then these lists are further merged, at one time, to eventually create one sorted list.

: A snapshot during a partition in external- memory 2-quicksort. A data is sequentially input through main memory and each element is compared to the pivot. We have one block of buffer space to accumulate elements smaller than the pivot, and one block of buffer space to accumulate elements larger than the pivot. Once any of the buffer blocks are full, they are written back to a particular location on disk, where either left or the right side of the array is being appended. It is important, for the recursive calls later, that the elements that are smaller/larger than the pivot are all contiguously placed.

: Snapshot of external-memory multi-way quicksort. Instead of one pivot, we find pivots and pull the entire dataset through memory. Based on comparisons with the pivots, each element is routed to the correct buffer block. Once the buffer block of any partition is filled, it is written back to memory and the buffer is emptied. After all data is pulled through main memory, we created partitions that quicksort can again recurse on. Once a partition is of size , the entire partition is read into main memory, sorted, and written back.

: To understand how much one block transfer can help in sorting, we analyze how many potential orderings of B elements (contents of one block) there are inside a memory-full of elements. There is a total of (M choose B) orderings, and this is a factor by which one memory transfer can reduce the total number of permutations remaining to be examined.

• Sorting is one of the best-known problems in computer science, and there is a large body of research optimizing sorting algorithms for different contexts.
• When data can not fit into main memory, the sorting algorithm needs to bring in small pieces of data into main memory and sort chunk by chunk.
• -way external mergesort is the algorithm of choice for when data is too large to fit into RAM. This algorithm merges many lists at one, thus making use of a large available memory.
• Analogously, it is possible to adapt quicksort to work optimally in external memory by choosing a larger set of pivots and thus partitioning data into many individual sub-partitions instead of just 2.

• To understand whether a sorting algorithm is optimal, it is important to understand how sorting lower bounds work. In case of internal memory, the key is understanding how much one comparison can contribute to eliminating permutations that are not the sorted order, and in external memory, we do the same, but by analyzing how much one block input can help us eliminate the permutations.

FAQ