External sorting is a generic term for a class of sorting algorithms that can handle massive amounts of data. External sorting is required when the data being sorted does not fit into the main memory of a computing device (usually RAM) and a slower kind of memory (usually a hard drive) needs to be used.

One example of external sorting is the external mergesort algorithm. For the sake of clarity, let us assume that 900 megabytes of data needs to be sorted using only 100 megabytes of RAM.

1. Read 100MB of the data in main memory and sort by some conventional method (usually quicksort).
2. Write the sorted data to disk.
3. Repeat steps 1 and 2 until all of the data is sorted in chunks of 100MB. Now you need to merge them into one single sorted output file.
4. Read the first 10MB of each sorted chunk (call them input buffers) in main memory (90MB total) and allocate the remaining 10MB for output buffer.
5. Perform a 9-way merging and store the result in the output buffer. If the output buffer is full, write it to the final sorted file. If any of the 9 input buffers gets empty, fill it with the next 10MB of its associated 100MB sorted chunk or otherwise mark it as exhausted if there is no more data in the sorted chunk and do not use it for merging.

The above described algorithm can be generalized by assuming that the amount of data to be sorted exceeds the available memory by a factor of K. Then, K chunks of data need to be sorted and a K-way merge has to be completed. If X is the amount of main memory available, there will be K input buffers and 1 output buffer of size X/(K+1) each. Depending on various factors (how fast the hard drive is, what is the value of K) better performance can be achieved if the output buffer is made larger (for example twice as large as one input buffer).

In the example, a single-pass merge was used. If the ratio of data to available main memory is particularly large, a multi-pass sorting is preferable. For example, merge only the first half of the sorted chunks, then the other half and now the problem has been reduced to merging just two sorted chunks. The exact number of passes depends on the above mentioned ratio, as well as the physical characteristics of the hard drive (transfer rate and seeking time). As a rule of thumb, do not perform more than 20-30 way merge.

If carefully implemented, external sorting can be done in-place (with no additional disk space required).

A description of the unix 'Sort' command

A quicksort example