External sorting

External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside in the slower external memory, usually a disk drive.

In the merge phase, the sorted subfiles are combined into a single larger file.

Like their cache-oblivious counterparts, asymptotically optimal external sorting algorithms achieve a running time (in Big O notation) of

During a merge pass, B elements from each sorted list are in internal memory, and the minimum is repeatedly outputted.

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.

Eventually, the reads become so small that more time is spent on disk seeks than data transfer.

Then the sorting process might look like this: Although this requires an additional pass over the data, each read is now 4 MB long, so only 1/5 of the disk's time is spent seeking.

Variations include using an intermediate medium like solid-state disk for some stages; the fast temporary storage needn't be big enough to hold the whole dataset, just substantially larger than available main memory.

Repeating the example above with 1 GB of temporary SSD storage, the first pass could merge 10×100 MB sorted chunks read from that temporary space to write 50x1 GB sorted chunks to HDD.

Given the lower cost of SSD capacity relative to RAM, SSDs can be an economical tool for sorting large inputs with very limited memory.

Like in-memory sorts, efficient external sorts require O(n log n) time: exponentially growing datasets require linearly increasing numbers of passes that each take O(n) time.

[4] Under reasonable assumptions at least 500 GB of data stored on a hard drive can be sorted using 1 GB of main memory before a third pass becomes advantageous, and many times that much data can be sorted before a fourth pass becomes useful.

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

pivots would not be fast enough to make the external distribution sort asymptotically optimal.