So after taking the time to sit down and actually watch Bentley's google lecture, Three Beautiful Quicksorts, it turns out that randomized pivot's are not faster than other methods. Specifically, according to Bently - who with McIlroy - rewrote the standard C library qsort function, we have the following from their paper, Engineering a Sort Function:
- $1.386\;\cdot n \lg n$ average comparisons using first, middle or a randomized pivot
- $1.188\;\cdot n \lg n$ average comparisons using a median of 3 pivot
- $1.094\;\cdot n \lg n$ average comparisons using a median of 3 medians pivot
According to the above paper:
Our final code therefore chooses the middle element of smaller arrays,
the median of the first, middle and last elements of a mid-sized
array, and the pseudo-median of nine evenly spaced elements of a large
I read the following in Data Structures Using C, by Tenenbaum, Langsam and Augenstein:
It is possible to speed up quicksort for sorted files by choosing a
random element of each subfile as the pivot value. If a file is known to be nearly sorted, this might be a good strategy ( although,
in that case choosing the middle element as a pivot would be even
better ). However, if nothing is known about the file, such a
strategy does not improve the worst case behaviour, since it is
possible (although improbably) that the random element chosen each
time might consistently be the smallest element of each subfile. As a
practical matter, sorted files are more common than a good random
number generator happening to choose the smallest element repeatedly.
In their book they use the Hoare partition scheme. Further down they say:
It can be shown, however, that on the average (over all files of size
$n$), the quicksort makes approximately $1.386 n \lg n$ comparisons
even in its unmodified version.
He's referring here to picking the first element as the pivot.
I think I just stumbled on the answer to how a deterministic selection of pivot outperforms a randomized one.
Question 9.3-3 in Cormen is, "Show how quicksort can be made to run in $O(n \lg n)$ time in the worst case."
The answer is to use deterministic selection to select the median element each time. Since deterministic selection runs in $O(n)$ time worst case, you get the worst case recursion $$T(n)=2T(n/2)+Θ(n)=Θ(n \lg n)$$ for this deterministic quicksort, admittedly with a large hidden constant factor in there.
I think that what Bentely is doing is an extension of this idea using a pseudo median. Bentely's paper references another paper which quantifies the quality of these pseudo medians.
The cost of computing the pseudo median is $\Theta(1)$ whereas finding the real median is $O(n)$. This is probably a big part of where his very small constant factor comes from. I assume that the paper Bentely references proves somehow that the pseudo median is "good enough" to guarantee a high enough percentage of good splits by the partition function to give the above run times.