Definition: Pick an element from the array (the pivot). Consider the first character (key) of the string (multikey). Partition the remaining elements into three sets: those whose corresponding character is less than, equal to, and greater than the pivot's character. Recursively sort the "less than" and "greater than" partitions on the same character. Recursively sort the "equal to" partition by the next character (key).
Also known as three-way radix quicksort.
Generalization (I am a kind of ...)
quicksort.
Aggregate child (... is a part of or used in me.)
Dutch national flag, key.
See also postman's sort, quicksort, ternary search tree.
Note: Especially good for strings. Fast Algorithms ... gives a good 3-way partition algorithm.
Author: PEB
Jon L. Bentley and Robert Sedgewick, Fast Algorithms for Sorting and Searching Strings, Proc. 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 360-369, January 1997.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 30 December 2005.
HTML page formatted Mon Feb 2 13:10:40 2015.
Cite this as:
Paul E. Black, "multikey Quicksort", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 30 December 2005. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/multikeyQuicksort.html