On Sunday, 17 November 2013 at 01:07:20 UTC, Ivan Kazmenko wrote:
Now, the assumption of picking a pivot in O(1) comparisons covers a broad variety of pivot choices, including first/last/middle/random element, median of three or five, median of medians, or any combination of these. The random pick fails in the following sense: if we seed the RNG, construct a killer case, and then start with the same seed, we get Theta(n^2) behavior reproduced.
Correction: this does *not* cover the median-of-medians case [1]. Median of medians does not fall under our assumption that selecting a pivot is O(1). It also actually guarantees O(n log n) worst case performance, but of course at a cost of being slower than your typical pivot selection on an average case.
[1] http://en.wikipedia.org/wiki/Median_of_medians Ivan Kazmenko.
