[Solved]: From Whence the Randomization in Randomized Quicksort

Problem Detail: 

Cormen talks briefly about the advantages of picking a random pivot in quicksort. However as pointed out here(4th to the last paragraph):

Using a random number generator to choose the positions is relatively expensive

So how is picking a random pivot actually implemented in practice, and how random is it? It can't be too expensive, since from what I understand one of quicksort's main advantages over other $\cal{O}(n \lg n)$ sorts is the small constant factors, and spending allot of cycles picking pivots would undermine that advantage.

EDIT

As an example, the C code from "Three Beautiful Quicksorts" actually calls the C library rand function:

int randint(int l, int u) {     return rand()%(u-l+1)+l; }  void quicksort(int l, int u) {     int i, m;     if (l >= u) return;     swap(l, randint(l, u));     m = l;     for (i = l+1; i <= u; i++)         if (x[i] < x[l])             swap(++m, i);     swap(l, m);     quicksort(l, m-1);     quicksort(m+1, u); } 

While the pivot picking code here is clearly $\cal{O}(1)$, it would seem that the hidden $c$ here is relatively high.

Asked By : Robert S. Barnes

Answered By : vonbrand

Take a look at McIllroy and Douglas' "A Killer Adversary for Quicksort" (Software -- Practice and Experience 29(4): 341-344 (1999)) or Crosby and Wallach's "Denial of Service via Algorithmic Complexity Attacks" for the reason behind randomizing. Quicksort behaves very badly if you pick (nearly) the largest/smallest as pivot each time. For randomization to make sense, it has to be random (if I know how you pick pivots deterministically, I can cook up an array that forces you to go into $O(n^2)$ behaviour, see the paper mentioned for details). But a fancy RNG is costlier than, say, taking 3 or another smallish odd number of elements, and pick the median of those as pivot, which is another way to counteract bad behaviour. So if you choose randomization, use a fast RNG seeded appropiately (probably a linear congruential scheme will be enough).

Algorithms can (and should) be compared by $O(\cdot)$, but if you are talking about different implementations of the same algorithm one must switch to more detailed analysis. In fact, Sedgewick and Flajolet in "An introduction to the analysis of algorithms" argue that one shouldn't use $T(n) = O(f(n))$ at all, but should strive to get $T(n) \sim f(n)$ type asymptotics.

Best Answer from StackOverflow

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