Definition: Any sort algorithm that uses external memory, such as tape or disk, during the sort. Since most common sort algorithms assume high-speed random access to all intermediate memory, they are unsuitable if the values to be sorted don't fit in main memory.
Specialization (... is a kind of me.)
balanced multiway merge, cascade merge sort, optimal polyphase merge sort, oscillating merge sort, polyphase merge sort, external radix sort, external quicksort.
See also internal sort, external merge, external memory algorithm.
Note: Algorithms may read the initial values from magnetic tape or write sorted values to disk, but this is not using external memory during the sort. Note that even though virtual memory may mask the use of disk, sorting sets of data much larger than main memory may be much faster using an explicit external sort.
See [Knuth98, vol. 3, Sect. 5.4] for an extensive treatment.
Geeta Chaudhry's PhD thesis which includes new external sort algorithms and comparisons with other external sort algorithms.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 17 December 2004.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "external sort", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/externalsort.html