Cormen talks briefly about the advantages of picking a random pivot in quicksort. However as pointed out [here](http://algoviz.org/OpenDSA/Books/OpenDSA/html/Quicksort.html)(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](http://www.catonmat.net/blog/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.