Worst-case performance of quickSort / getPivot

[Ivan Kazmenko]

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.