(definition)
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.
Author: PEB
The PhD dissertation of Geeta Chaudhry (Parallel Out-of-Core Sorting: The Third Way, Dartmouth Computer Science Technical Report TR2004-517, September 2004.) 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 Black.
Entry modified 23 December 2013.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "external sort", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 23 December 2013. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/externalsort.html