randomized quicksort

Ordinary quicksort sorts by picking a 'pivot,' splitting the rest into items smaller and larger than it, and sorting the two halves. It is fast when the pivot lands near the middle, but a bad fixed choice (say always the first element) can be disastrous on already-sorted data, degrading to O(n^2). Randomized quicksort removes that vulnerability by choosing the pivot at random each time, so no particular input can be the worst case — the adversary cannot predict your coin flips.

Precisely: at each recursive call, pick a pivot uniformly at random from the current subarray, partition around it, and recurse on both sides. The algorithm always sorts correctly; only the running time depends on the random choices. The expected number of comparisons is the elegant part. Let X_ij be the indicator that the i-th and j-th smallest elements are ever compared. Two elements are compared exactly when one of them is the first among that whole range to be chosen as a pivot, which by symmetry happens with probability 2/(j - i + 1). By linearity of expectation, the expected total comparisons is sum over i < j of 2/(j - i + 1), which works out to about 2 n ln n = O(n log n). No independence assumption is needed for this expectation — linearity carries it.

Randomized quicksort matters because it gives the practical speed of quicksort with a guarantee that does not depend on the input order: its expected time is O(n log n) for every input, and a Chernoff-style argument shows it is O(n log n) with high probability too. It is a textbook illustration of converting a fragile average-case story into a robust randomized one. The honest caveat: the worst case is still O(n^2) — an unlucky run of pivot choices can be slow — and the O(n log n) is an expectation over the algorithm's coins, not a hard bound. Choosing the median exactly would guarantee O(n log n) deterministically, but finding the median costs more than the savings, so randomness is the pragmatic win.