Randomized quicksort & expected analysis

Move the worst case off the input

Plain quicksort fails on sorted input because the input controls the pivot. RANDOMIZED-PARTITION breaks that link: before partitioning, pick a uniform random index $k\in [p,r]$, swap $A[k]\leftrightarrow A[r]$, then run ordinary PARTITION. Now the pivot is a random element, so no fixed input can force bad behaviour — an adversary would have to predict the coin flips. The worst case is still $\Theta (n^2)$ in principle, but it now depends on the randomness, not the data, and occurs with negligible probability. We therefore analyze expected running time, which is $\Theta (n\lg n)$ for every input.

The indicator-variable proof (the examined argument)

Let the sorted order be $z_1<z_2<\cdots <z_n$ and define $Z_{ij}=\{z_i,\dots ,z_j\}$. Two facts:

1. Lemma (when compared). $z_i$ and $z_j$ are compared iff the first pivot chosen from $Z_{ij}$ is $z_i$ or $z_j$; any interior element chosen first splits them apart forever. And no pair is compared twice.
2. Probability. All $j-i+1$ elements of $Z_{ij}$ are equally likely to be the first pivot, and exactly two of them ($z_i,z_j$) cause a comparison, so $\mathrm{Pr}[z_i\text{ vs }{z}_j]=\frac{2}{j-i+1}$.

Let $X_{ij}=1\{z_i\text{ compared with }{z}_j\}$. By linearity of expectation,

$$E[X]=\sum _{i<j}\frac{2}{j-i+1}=\sum _{i=1}^{n-1}\sum _{k=1}^{n-i}\frac{2}{k+1}<\sum _{i=1}^{n-1}2H_n=O(n\lg n),$$

where $H_n=\sum 1/k=\ln n+O(1)$ is the harmonic series. Since quicksort's time is $O(n+X)$, the expected running time is $O(n\lg n)$ — unconditionally, on any input.

Worked example

With a fixed seed, randomized quicksort sorts $⟨5,2,9,1,5,6,3,8,5,0,7,4⟩$ (note the duplicate $5$s) to $⟨0,1,2,3,4,5,5,5,6,7,8,9⟩$. Because the output of a correct sort is deterministic even though the pivot choices are random, the exercise checks the sorted result against Python's sorted() — never the internal coin flips.