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.


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.

  • $\begingroup$ It's not expensive. It is certainly $O(1)$. And you don't need any fancy kind of randomness. The regular multiply, add, divide is fine. Though apparently the authors of that text thought it's too expensive. It's not something you need to worry much about, though. $\endgroup$ Apr 18, 2013 at 18:22
  • 1
    $\begingroup$ @KarolisJuodelė Actually, if you want to map the random element over all indices the of input list, you must calculate at least $O(\log n)$ time to simply read the index. And you need $n$ of those pivots, so that's $O(n \log n)$ just generating the necessary bits. But, of course, RAM model et cetera, et cetera, et cetera ... $\endgroup$
    – Pål GD
    Apr 18, 2013 at 18:27

2 Answers 2


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.

  • $\begingroup$ So the real main reason for "randomizing" the pivot choice is more a security reason than a asymptotics reason? $\endgroup$ Apr 19, 2013 at 5:25
  • $\begingroup$ @RobertS.Barnes No, the main reason is the expected running time. $\endgroup$
    – Pål GD
    Apr 19, 2013 at 7:11
  • $\begingroup$ A linear congruential generator will not be enough. paper. $\endgroup$
    – adrianN
    Apr 19, 2013 at 8:10
  • 1
    $\begingroup$ this theory is based on an "adversary" that attempts to cause an algorithmic slowdown via internal knowledge of the algorithm. so its applicable more in cryptography and not so much general algorithmic complexity where "pathological" cases of sort orders appearing at random are basically negligible. $\endgroup$
    – vzn
    Apr 20, 2013 at 18:45
  • $\begingroup$ @PålGD What do you make of Bentley's results which show a deterministic choice of pivot significantly outperforming a randomized one? $\endgroup$ Apr 22, 2013 at 9:30

So after taking the time to sit down and actually watch Bentley's google lecture, Three Beautiful Quicksorts, it turns out that randomized pivot's are not faster than other methods. Specifically, according to Bently - who with McIlroy - rewrote the standard C library qsort function, we have the following from their paper, Engineering a Sort Function:

  • $1.386\;\cdot n \lg n$ average comparisons using first, middle or a randomized pivot
  • $1.188\;\cdot n \lg n$ average comparisons using a median of 3 pivot
  • $1.094\;\cdot n \lg n$ average comparisons using a median of 3 medians pivot

According to the above paper:

Our final code therefore chooses the middle element of smaller arrays, the median of the first, middle and last elements of a mid-sized array, and the pseudo-median of nine evenly spaced elements of a large array.

I read the following in Data Structures Using C, by Tenenbaum, Langsam and Augenstein:

It is possible to speed up quicksort for sorted files by choosing a random element of each subfile as the pivot value. If a file is known to be nearly sorted, this might be a good strategy ( although, in that case choosing the middle element as a pivot would be even better ). However, if nothing is known about the file, such a strategy does not improve the worst case behaviour, since it is possible (although improbably) that the random element chosen each time might consistently be the smallest element of each subfile. As a practical matter, sorted files are more common than a good random number generator happening to choose the smallest element repeatedly.

In their book they use the Hoare partition scheme. Further down they say:

It can be shown, however, that on the average (over all files of size $n$), the quicksort makes approximately $1.386 n \lg n$ comparisons even in its unmodified version.

He's referring here to picking the first element as the pivot.


I think I just stumbled on the answer to how a deterministic selection of pivot outperforms a randomized one.

Question 9.3-3 in Cormen is, "Show how quicksort can be made to run in $O(n \lg n)$ time in the worst case."

The answer is to use deterministic selection to select the median element each time. Since deterministic selection runs in $O(n)$ time worst case, you get the worst case recursion $$T(n)=2T(n/2)+Θ(n)=Θ(n \lg n)$$ for this deterministic quicksort, admittedly with a large hidden constant factor in there.

I think that what Bentely is doing is an extension of this idea using a pseudo median. Bentely's paper references another paper which quantifies the quality of these pseudo medians.

The cost of computing the pseudo median is $\Theta(1)$ whereas finding the real median is $O(n)$. This is probably a big part of where his very small constant factor comes from. I assume that the paper Bentely references proves somehow that the pseudo median is "good enough" to guarantee a high enough percentage of good splits by the partition function to give the above run times.

  • $\begingroup$ But this is average complexity and not worst time complexity, right? $\endgroup$
    – Pål GD
    Apr 22, 2013 at 11:30
  • 1
    $\begingroup$ @PålGD Yes, but we're always talking about average case when it comes to quicksort. And as I suspected, and Tenenbaum confirms, picking a random pivot doesn't eliminate quicksort's worstcase behaviour and in fact the randomized quicksort performs no better on average than the one which picks the first element as it's pivot. That's also what Bentley said above. $\endgroup$ Apr 23, 2013 at 6:28
  • 2
    $\begingroup$ No, we are not always talking about average case complexity with quicksort. Expected running time is over the randomness of the algorithm, but is worst case over inputs. Average case complexity assumes inputs come from a distribution. This is a big assumption: often your arrays will have structure, which means they're nothing like random. On the other hand there are no bad inputs for randomized quick sort - just bad randomness, but that is much more unlikely than a bad file if you have a reasonable PRG $\endgroup$ Apr 23, 2013 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.