Re: Randomisation for ensuring nlogn complexity in quicksort

On Mon, Jul 1, 2013 at 4:32 PM, Robert Haas <robertmhaas@gmail.com> wrote:
>> This shouldn't be too complex, and should give us a fixed nlogn complexity even for wild data sets, without
affectingexisting normal data sets that are present in every day transactions. I even believe that those data sets will
alsobenefit from the above optimisation. 
>
> The only method of selecting a pivot for quicksort that obtain O(n lg
> n) run time with 100% certainty is have a magical oracle inside the
> computer that tells you in fixed time and with perfect accuracy which
> pivot you should select.


Doesn't a linear median algorithm (say median of medians) get you O(n lg n)?

Granted, with a huge constant (I think 4)... but it should still be O(n lg n).