[Solved]: Are there adversarial inputs for randomized quicksort?

Problem Detail: 

Someone recently claimed that there's an adversarial input for randomized quicksort; he referenced this paper. This defies my intuition because there are results that say that randomized quicksort runs in $O(n \log n)$ time with high probability. (See, for example, the book Randomized Algorithms by Motwani&Raghavan.) I am refering to the version of randomized quicksort that picks the pivot uniformly at random at each recursive call.

So my question is: are there indeed adversarial inputs for randomized quicksort? Please give an intuitive reason as to why such an input can exist.

Update. It seems to me that the adversary in the paper is granted unrealistic capabilities (generate array on the fly), which explains why it can make any quicksort perform poorly. Under reasonable assumptions I would say there is indeed no adversarial input for randomized quicksort.

Asked By : blazs

Answered By : Yuval Filmus

The analysis of randomized quicksort is independent of the input. While there might be better inputs and worse inputs, the upper bound given by the analysis works for every single input.

You can go over the proof in slides of Xi Chen, for example, who proves that whatever the input, randomized quicksort runs in expected time $O(n\log n)$. (I don't know whether your high probability claim is true as well, though it sounds plausible.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/55382