NIST

multikey Quicksort

(algorithm)

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

Implementation

Fast Algorithms paper, demos, and code (C)

More information

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.


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 8 March 2021.
HTML page formatted Mon Mar 8 10:01:45 2021.

Cite this as:
Paul E. Black, "multikey Quicksort", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 8 March 2021. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/multikeyQuicksort.html