# What is the advantage of Randomized Quicksort?

In their book Randomized Algorithms, Motwani and Raghavan open the introduction with a description of their RandQS function -- Randomized quicksort -- where the pivot, used for partitioning the set into two parts, is chosen at random.

I have been racking my (admittedly somewhat underpowered) brains over this for some time, but I haven't been able to see what advantage this algorithm has over simply picking, say, the middle element (in index, not size) each time.

I suppose what I can't see is this: if the initial set is in a random order, what is the difference between picking an element at a random location in the set and picking an element at a fixed position?

Can someone enlighten me, in fairly simple terms?

If however your input array is not really in random order (which happens to be the case in almost all practical scenarios) then one needs to either "preshufle" the array in order for the elements in it to be placed in random order, or (equivalently) always take a random element as a pivot. This ensures the partitioning phase of quicksort partitions the arrays into sub-arrays of almost equal size and hence that the expected running time remains $O(n\log n)$
• It may be worth mentioning that while there's a theoretical guarantee to randomizing (because you get $O(n\log n)$ worst case instead of $O(n^2)$) prerandomizing data can lead to practical speedups as well in some applications. Bad quicksort cases are more common than one might expect (depending obviously on implementation). – SamM Dec 24 '12 at 21:30
• When you say "distributed uniformly at random", you mean that each of the $n!$ permutations has equal probability of $\frac{1}{n!}$? – Robert S. Barnes Apr 19 '13 at 5:50