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.