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 < \dots < 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 $\Pr[z_i \text{ vs } z_j] = \dfrac{2}{j-i+1}$.

Let $X_{ij}=\mathbb{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 $\langle 5,2,9,1,5,6,3,8,5,0,7,4\rangle$ (note the duplicate $5$s) to $\langle 0,1,2,3,4,5,5,5,6,7,8,9\rangle$. 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.