(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 [Wikipedia], 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 College Ph.D. Dissertation 7, 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 26 July 2021.
HTML page formatted Mon Jul 26 09:50:40 2021.
Cite this as:
Paul E. Black, "external sort", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 26 July 2021. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/externalsort.html