Chapter 7: Quicksort: Description, Performance, and Analysis

The algorithm works by selecting a pivot element — defaulting to the last element in the basic version — and partitioning the array so that all elements less than or equal to the pivot appear to its left and all greater elements to its right, after which the two subarrays are sorted recursively with no additional combine step needed. Quicksort is in-place, requiring only constant extra space, but its performance is highly sensitive to pivot quality: the worst case arises on already sorted or reverse-sorted input, where partitioning produces subarrays of size n–1 and 0, yielding the recurrence T(n) = T(n–1) + Θ(n) and a Θ(n²) running time with recursion depth Θ(n), while the best case of perfectly balanced splits gives T(n) = 2T(n/2) + Θ(n) = Θ(n log n). The randomized variant addresses this vulnerability by selecting the pivot uniformly at random, ensuring that no particular input order can reliably trigger worst-case behavior and guaranteeing an expected running time of O(n log n) across all inputs. This is formally proven using indicator random variables, where the probability that any two elements i and j are ever compared equals 2/(j – i + 1), and summing over all pairs yields E[X] = O(n log n) total expected comparisons. Practical optimizations such as median-of-three pivot selection — taking the median of the first, middle, and last elements — and tail-recursion elimination further improve real-world performance by reducing the chance of bad pivots and minimizing stack depth, without changing the asymptotic behavior.