Multi-key quicksort

Three-way radix quicksort, also known as multi-key quicksort, is an algorithm for sorting strings. This hybrid of quicksort and radix sort was originally suggested by P. Shackleton and reported in C.A.R. Hoare's seminal paper 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.

Description

The three-way radix quicksort algorithm sorts an array of N (pointers to) strings in lexicographic order. It is assumed that all strings are of equal length K; 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

function sort(a : array of string, d : integer):
    if length(a) ≤ 1 or d ≥ K:
        return
    p ← pivot(a, d)
    i, j ← partition(a, d, p)
    sort(a[0..i], d)
    sort(a[i..j], d+1)
    sort(a[j..length(a)], d)

The pivot function must return a single character. Bentley and Sedgewick suggest either picking the median of a[0][d], ..., a[length(a)−1][d] or some random character in that range. The partition function is a variant of the one used in ordinary three-way quicksort: it rearranges a so that all of a[0], ..., a[i−1] have an element at position d that is less than p, a[i], ..., a[j−1] have p at position d, and strings from j onward have a d'th element larger than p.

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.