6 ms·

Randomized Quicksort?

• gjm11 16y ago
  In typical cases the "killer adversary" will still be able to make a good guess at when the pivot is being found, and drive the quicksort routine into bad behaviour, even when the pivot selection is randomized. (Of course that means that the resulting array will typically not produce bad behaviour if it's sorted with the RNG in a different initial state, whereas for nonrandomized quicksorts the adversary produces an array that will reliably provoke quadratic-time behaviour.)