External sorting

External sorting algorithms can be analyzed in the external memory model. In this model, a cache or internal memory of size M and an unbounded external memory are divided into blocks of size B, and the running time of an algorithm is determined by the number of memory transfers between internal and external memory. Like their cache-oblivious counterparts, asymptotically optimal external sorting algorithms achieve a running time (in Big O notation) of ${\displaystyle O\left({\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}\right)}$.

One example of external sorting is the external merge sort algorithm, which is a K-way merge algorithm. It sorts chunks that each fit in RAM, then merges the sorted chunks together.[1][2]

The algorithm first sorts M items at a time and puts the sorted lists back into external memory. It then recursively does a ${\displaystyle {\tfrac {M}{B}}}$-way merge on those sorted lists. To do this merge, B elements from each sorted list are loaded into internal memory, and the minimum is repeatedly outputted.

For example, for sorting 900 megabytes of data using only 100 megabytes of RAM:

1. Read 100 MB of the data in main memory and sort by some conventional method, like quicksort.
2. Write the sorted data to disk.
3. Repeat steps 1 and 2 until all of the data is in sorted 100 MB chunks (there are 900MB / 100MB = 9 chunks), which now need to be merged into one single output file.
4. Read the first 10 MB (= 100MB / (9 chunks + 1)) of each sorted chunk into input buffers in main memory and allocate the remaining 10 MB for an output buffer. (In practice, it might provide better performance to make the output buffer larger and the input buffers slightly smaller.)
5. Perform a 9-way merge and store the result in the output buffer. Whenever the output buffer fills, write it to the final sorted file and empty it. Whenever any of the 9 input buffers empties, fill it with the next 10 MB of its associated 100 MB sorted chunk until no more data from the chunk is available. This is the key step that makes external merge sort work externally -- because the merge algorithm only makes one pass sequentially through each of the chunks, each chunk does not have to be loaded completely; rather, sequential parts of the chunk can be loaded as needed.

Historically, instead of a sort, sometimes a replacement-selection algorithm[3] was used to perform the initial distribution, to produce on average half as many output chunks of double the length.

External distribution sort is analogous to quicksort. The algorithm finds approximately ${\displaystyle {\tfrac {M}{B}}}$ pivots and uses them to divide the N elements into approximately equally sized subarrays, each of whose elements are all smaller than the next, and then recurse until the sizes of the subarrays are less than the block size. When the subarrays are less than the block size, sorting can be done quickly because all reads and writes are done in the cache, and in the external memory model requires ${\displaystyle O(1)}$ operations.

However, finding exactly ${\displaystyle {\tfrac {M}{B}}}$ pivots would not be fast enough to make the external distribution sort asymptotically optimal. Instead, we find slightly less pivots. To find these pivots, the algorithm splits the N input elements into ${\displaystyle {\tfrac {N}{M}}}$ chunks, and takes every ${\displaystyle {\sqrt {\tfrac {M}{16B}}}}$ elements, and recursively uses the median of medians algorithm to find ${\displaystyle {\sqrt {\tfrac {M}{B}}}}$ pivots.[6]

There is a duality, or fundamental similarity, between merge- and distribution-based algorithms.[7]

The Sort Benchmark, created by computer scientist Jim Gray, compares external sorting algorithms implemented using finely tuned hardware and software. Winning implementations use several techniques:

• Using parallelism
  • Multiple disk drives can be used in parallel in order to improve sequential read and write speed. This can be a very cost-efficient improvement: a Sort Benchmark winner in the cost-centric Penny Sort category uses six hard drives in an otherwise midrange machine.[8]
  • Sorting software can use multiple threads, to speed up the process on modern multicore computers.
  • Software can use asynchronous I/O so that one run of data can be sorted or merged while other runs are being read from or written to disk.
  • Multiple machines connected by fast network links can each sort part of a huge dataset in parallel.[9]
• Increasing hardware speed
  • Using more RAM for sorting can reduce the number of disk seeks and avoid the need for more passes.
  • Fast external memory like solid-state drives can speed sorts, either if the data is small enough to fit entirely on SSDs or, more rarely, to accelerate sorting SSD-sized chunks in a three-pass sort.
  • Many other factors can affect hardware's maximum sorting speed: CPU speed and number of cores, RAM access latency, input/output bandwidth, disk read/write speed, disk seek time, and others. "Balancing" the hardware to minimize bottlenecks is an important part of designing an efficient sorting system.
  • Cost-efficiency as well as absolute speed can be critical, especially in cluster environments where lower node costs allow purchasing more nodes.
• Increasing software speed
  • Some Sort Benchmark entrants use a variation on radix sort for the first phase of sorting: they separate data into one of many "bins" based on the beginning of its value. Sort Benchmark data is random and especially well-suited to this optimization.
  • Compacting the input, intermediate files, and output can reduce time spent on I/O, but is not allowed in the Sort Benchmark.
  • Because the Sort Benchmark sorts long (100-byte) records using short (10-byte) keys, sorting software sometimes rearranges the keys separately from the values to reduce memory I/O volume.

• Mainframe sort merge
• External memory algorithm
• Funnelsort
• Cache-oblivious distribution sort

• STXXL, an algorithm toolkit including external mergesort
• An external mergesort example
• A K-Way Merge Implementation
• External-Memory Sorting in Java
• A sample pennysort implementation using Judy Arrays
• Sort Benchmark