Multi-key quicksort


Multi-key quicksort, also known as three-way radix quicksort, is an algorithm for sorting strings. This hybrid of quicksort and radix sort was originally suggested by P. Shackleton, as reported in one of C.A.R. Hoare's seminal papers on quicksort; its modern incarnation was developed by Jon Bentley and Robert Sedgewick in the mid-1990s. The algorithm is designed to exploit the property that in many problems, strings tend to have shared prefixes.
One of the algorithm's uses is the construction of suffix arrays, for which it was one of the fastest algorithms as of 2004.

Description

The three-way radix quicksort algorithm sorts an array of strings in lexicographic order. It is assumed that all strings are of equal length ; if the strings are of varying length, they must be padded with extra elements that are less than any element in the strings. The pseudocode for the algorithm is then
algorithm sort is
if length ≤ 1 or d ≥ K then
return
p := pivot
i, j := partition
sort
sort
sort, d)
The function must return a single character. Bentley and Sedgewick suggest either picking the median of or some random character in that range. The partition function is a variant of the one used in ordinary three-way quicksort: it rearranges so that all of have an element at position that is less than, have at position, and strings from onward have a 'th element larger than.
Practical implementations of multi-key quicksort can benefit from the same optimizations typically applied to quicksort: median-of-three pivoting, switching to insertion sort for small arrays, etc.