The Average Case of Quicksort

This post is the formal companion to the quicksort chapter in my data structures course. In the course notes, we justify quicksort's average-case performance mostly by intuition: a good pivot splits the array into two reasonably balanced pieces, and a sequence of reasonably balanced splits leads to $O(n\log n)$ work. Here we do the calculation.

The prerequisites are modest. You should know how quicksort partitions around a pivot, what Big-O notation means, what logarithms are, and the basic idea of probability. You do not need a discrete mathematics course. When we use a tool that may be new, such as expected value, I will spell out what it means.

We will assume the array contains $n$ distinct values and that quicksort chooses its pivot uniformly at random from the current slice each time it partitions. If your implementation always chooses the first item as pivot, this is the same kind of analysis you get after randomly shuffling the input first.

Quicksort sorts by partitioning around a pivot: values smaller than the pivot go to one side, values larger than the pivot go to the other, and then quicksort recursively sorts the two sides. Almost all of the algorithmic work we care about here is in comparisons: each partition step compares values against the pivot. So we will count comparisons, averaged over all the random pivot choices.

The final answer will be that random-pivot quicksort makes

$$2(n+1)H_n-4n$$

comparisons on average, where

$$H_n=1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}.$$

For large $n$, that is about

$$1.39n\lg n.$$

So the familiar $O(n\log n)$ average-case running time is not just a slogan. It comes from a precise count of the comparisons quicksort is likely to make.

Averaging a sum one pair at a time

The total number of comparisons is hard to track directly, because it depends on the whole sequence of pivots. Instead of trying to follow the whole run at once, we will look at one pair of values at a time.

Number the values by their place in sorted order. Let $z_1$ be the smallest value, $z_2$ the next smallest, and so on up to $z_n$, the largest. This numbering is not the array index during the algorithm. It is the value's rank in sorted order.

Take any two values, $z_i$ and $z_j$, with $i<j$. During one run of quicksort, this pair is either compared exactly once or never compared at all.

It cannot be compared more than once. Two values are compared only when one of them is the pivot in a partition step. Once a value is chosen as a pivot, it is placed in its final sorted position and is never used in another partition. So the same two values cannot meet again later as pivot and non-pivot.

Now define a small counter for this pair:

$$X_{ij}=\{\begin{array}{ll}1& \text{if }{z}_i\text{ and }{z}_j\text{ are compared},\\ 0& \text{otherwise.}\end{array}$$

The total number of comparisons in the whole run is the sum of these little counters over all pairs:

$$X=\sum _{i<j}{X}_{ij}.$$

For example, if $z_2$ and $z_6$ are compared, then $X_{2,6}$ contributes $1$ to the total. If they are not compared, it contributes $0$.

Now we average. The expected value of a random quantity is its long-run average: if you ran the same randomized algorithm many times and averaged the result, the average would approach the expected value. We write $E[X]$ for the expected value of $X$.

The key rule we need is that the expected value of a sum is the sum of the expected values:

$$E[X]=E\left[\sum _{i<j}{X}_{ij}\right]=\sum _{i<j}E[X_{ij}].$$

In words: to find the average total number of comparisons, we can add up the average contribution of each pair. This rule works even though the different pair counters are not independent.

Each $X_{ij}$ is only $0$ or $1$. Its average is therefore just the probability that it is $1$. If a pair is compared with probability $p$, then over many runs it contributes $1$ about a $p$ fraction of the time and $0$ the rest of the time, so its average contribution is $p$.

Therefore

$$E[X_{ij}]=\mathrm{Pr}[z_i\text{ and }{z}_j\text{ are compared}],$$

and the expected total number of comparisons is

$$E[X]=\sum _{i<j}\mathrm{Pr}[z_i\text{ and }{z}_j\text{ are compared}].$$

Now we need that probability.

When are two values compared?

Consider the values $1$ through $8$, already in sorted order, so $z_i=i$. Take the pair $2$ and $6$, and look at the block of values between them, ends included: $\{2,3,4,5,6\}$.

The key fact is this: $2$ and $6$ are compared if and only if the first pivot chosen from that block is either $2$ or $6$.

To see why, follow what happens as pivots are chosen. As long as no pivot comes from the block $\{2,3,4,5,6\}$, all five of those values stay together in one slice. A pivot from outside the block cannot separate them. A pivot of $1$ is smaller than all five, so they all go to its right. A pivot of $7$ or $8$ is larger than all five, so they all go to its left. Either way, the block stays whole.

So the first pivot that falls inside the block is the first one to touch these values, and there are three cases:

• The first such pivot is $2$. Then $2$ is compared against every value in its slice, and $6$ is still in that slice, so $2$ and $6$ are compared.
• The first such pivot is $6$. By the same reasoning, $6$ is compared against $2$.
• The first such pivot is a middle value, $3$, $4$, or $5$. Say it is $4$. Partitioning around $4$ sends $2$ and $3$ to its left and $5$ and $6$ to its right. Now $2$ and $6$ sit in different slices, and nothing ever brings them back together, so they are never compared. Each is compared against $4$, but not against each other.

So $2$ and $6$ are compared exactly when the first pivot from the block is one of the two ends, not one of the middle values.

The probability

The same reasoning works for any pair. The block between $z_i$ and $z_j$ is

$$\{z_i,z_{i+1},\dots ,z_j\}.$$

This block has

$$j-i+1$$

values: it starts at position $i$, ends at position $j$, and includes both ends.

The values in this block stay together until one of them is chosen as a pivot. Once the first pivot from this block is chosen, there are two possibilities:

• If the first pivot from the block is $z_i$ or $z_j$, then the pair is compared.
• If the first pivot from the block is one of the values strictly between them, then the pair is separated and is never compared.

Because pivots are chosen at random, the first value chosen from this block is equally likely to be any of the $j-i+1$ values in the block. One way to picture this is to imagine that the values in the block are waiting in a random order to become pivots. The one that appears first in that random order is equally likely to be any of them.

There are $j-i+1$ possible first pivots from the block. Exactly two of them, $z_i$ and $z_j$, make the pair get compared. Therefore

$$\mathrm{Pr}[z_i\text{ and }{z}_j\text{ are compared}]=\frac{2}{j-i+1}.$$

The closer two values are in sorted order, the more likely they are compared. Neighbors, where $j=i+1$, have a block of two and are compared with probability $2/2=1$, always. The smallest and largest values have a block of $n$ and are compared with probability only $2/n$.

Adding it up

Now put that probability into the expected-value sum:

$$E[X]=\sum _{i<j}\frac{2}{j-i+1}.$$

We could add this by looping over all choices of $i$ and $j$, but it is cleaner to group pairs by how far apart they are in sorted order.

Let

$$d=j-i.$$

This $d$ is the gap between the two values. If $d=1$, the values are neighbors in sorted order. If $d=2$, there is one value between them. In general, a gap of $d$ means the block from $z_i$ to $z_j$ has $d+1$ values, so each such pair is compared with probability

$$\frac{2}{d+1}.$$

How many pairs have gap $d$? The smaller value can be $z_1,z_2,\dots ,z_{n-d}$. After that, the larger value is forced: it must be $d$ positions later. So there are $n-d$ pairs with gap $d$.

Therefore

$$E[X]=\sum _{d=1}^{n-1}(n-d)\frac{2}{d+1}.$$

This formula is already the exact average number of comparisons. Now we simplify it.

Set $k=d+1$. When $d=1$, $k=2$. When $d=n-1$, $k=n$. Also, since $d=k-1$,

$$n-d=n-(k-1)=n+1-k.$$

So the sum becomes

$$E[X]=2\sum _{k=2}^n\frac{n+1-k}{k}.$$

Split the fraction:

$$\frac{n+1-k}{k}=\frac{n+1}{k}-1.$$

Then

$$E[X]=2\sum _{k=2}^n\left(\frac{n+1}{k}-1\right).$$

There are two pieces here:

$$\sum _{k=2}^n\frac{n+1}{k}=(n+1)\left(\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}\right),$$

and

$$\sum _{k=2}^{n}1=n-1.$$

Therefore

$$E[X]=2\left((n+1)\left(\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}\right)-(n-1)\right).$$

The sum

$$1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}$$

is called the $n$th harmonic number and is written $H_n$. Since

$$\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}=H_n-1,$$

we get

$$E[X]=2\left((n+1)(H_n-1)-(n-1)\right).$$

Expanding the expression gives the standard exact formula:

$$E[X]=2(n+1)H_n-4n.$$

That is the average number of comparisons made by random-pivot quicksort on $n$ distinct values.

Why this is O(n log n)

The exact formula contains $H_n$, so we need to know how fast $H_n$ grows.

The harmonic number

$$H_n=1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}$$

grows like $\ln n$. Intuitively, this sum is a discrete version of the area under the curve $1/x$. The area under $1/x$ from $1$ to $n$ is $\ln n$, so the sum $1+1/2+\cdots +1/n$ grows at the same logarithmic rate.

That means

$$H_n=O(\log n).$$

So from the exact formula,

$$E[X]=2(n+1)H_n-4n,$$

the main term grows like $n\log n$. The $-4n$ part is only linear, and the $2(n+1)$ factor in front of $H_n$ is proportional to $n$. Therefore the expected number of comparisons is

$$O(n\log n).$$

This is the formal version of the intuition from the course notes: random pivots tend to produce enough reasonably balanced splitting that the average cost is logarithmic levels of partitioning, with about $n$ comparison work per level.

The leading constant

The exact formula also tells us the leading constant. Since $H_n$ grows like $\ln n$, the dominant part of

$$2(n+1)H_n-4n$$

is

$$2n\ln n.$$

Computer science usually writes sorting lower bounds and comparison counts with base-two logarithms. Since

$$\ln n=(\ln 2)(\lg n),$$

we get

$$2n\ln n=2\ln 2\cdot n\lg n.$$

And because

$$2\ln 2\approx 1.386,$$

random-pivot quicksort makes about

$$1.39n\lg n$$

comparisons on average, ignoring lower-order terms.

No comparison sort can average fewer than about $n\lg n$ comparisons in the leading term, so quicksort's random-pivot average is only about forty percent above that floor. That is the precise sense in which quicksort is fast on average, and it stands well clear of the $O(n^2)$ behavior that bad pivot choices can produce.