(algorithm)
Definition: Read the M/2 first and last elements into a buffer (the buffer acts like the pivot in quicksort), and sort them. Read the next element from the beginning or end to balance writing. If the next element is less than the least of the buffer, write it to available space at the beginning. If greater than the greatest, write it to the end. Otherwise write the greatest or least of the buffer, and put the next element in the buffer. Keep the maximum lower and minimum upper keys written to avoid resorting middle elements that are in order. When done, write the buffer. Recursively sort the smaller partition, and loop to sort the remaining partition.
Generalization (I am a kind of ...)
external sort, in-place sort.
Aggregate child (... is a part of or used in me.)
partition, divide and conquer, recursion.
See also quicksort.
Note: Performance is terrible if the external memory does not have random (direct) access.
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 16 November 2009.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "external quicksort", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 16 November 2009. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/externalQuicksort.html