Why Randomize Pivot Selection?
Any deterministic Quicksort that picks a fixed index ($A[lo]$, $A[hi]$, or even $A[mid]$) has inputs for which every partition is $0 : (n-1)$, requiring $\sum_{k=1}^{n-1} k = \frac{n(n-1)}{2} = \Theta(n^2)$ comparisons. Randomized Quicksort defeats fixed-input adversaries by either shuffling the array upfront (Knuth-Fisher-Yates) or picking a pivot index uniformly at random from $\{lo, \dots, hi\}$ at every recursive step. The expected runtime then holds over the algorithm's internal random coin flips for every input array of $n$ distinct elements.
Let $z_1 < z_2 < \dots < z_n$ denote the $n$ distinct elements of the input array in sorted order (by rank). Define the indicator random variable: $$X_{ij} = \mathbb{I}\{\text{elements } z_i \text{ and } z_j \text{ are compared at any point during Randomized Quicksort}\} \quad (1 \le i < j \le n)$$ Because every comparison in Quicksort compares some element against the current pivot, and the pivot is never included in either recursive call, any pair $(z_i, z_j)$ is compared at most once. Thus the total number of comparisons is $X = \sum_{i=1}^{n-1}\sum_{j=i+1}^{n} X_{ij}$.
Crucial Observation: Consider the set of elements $Z_{ij} = \{z_i, z_{i+1}, \dots, z_j\}$ of cardinality $j - i + 1$. So long as no pivot is chosen from $Z_{ij}$, the entire set $Z_{ij}$ remains together in the same recursive subarray (either all strictly less than the pivot, or all strictly greater than the pivot). The very first time a pivot $p$ is chosen from $Z_{ij}$:
- If $p = z_i$ or $p = z_j$, then $z_i$ and $z_j$ are compared during that partition pass ($X_{ij} = 1$).
- If $z_i < p < z_j$, then $z_i$ is placed in the left partition ($< p$) and $z_j$ is placed in the right partition ($> p$); they are permanently separated and will never be compared ($X_{ij} = 0$).
Since each of the $j - i + 1$ elements in $Z_{ij}$ is equally likely to be the first one chosen as a pivot from $Z_{ij}$:
$$\Pr[X_{ij} = 1] = \frac{2}{j - i + 1}$$Summing the Harmonic Series: Where $1.386\,n \log_2 n$ Comes From
By linearity of expectation (which holds even though the indicator variables $X_{ij}$ are not mutually independent!):
$$\mathbb{E}[X] = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \frac{2}{j - i + 1}$$Substitute the span length $k = j - i$ (so $k$ ranges from $1$ to $n - 1$, and there are $n - k$ pairs with span $k$):
$$\mathbb{E}[X] = \sum_{k=1}^{n-1} (n - k) \frac{2}{k + 1} = 2(n + 1)\sum_{k=1}^{n-1}\frac{1}{k + 1} - 2(n - 1) = 2(n + 1)(H_n - 1) - 2(n - 1) = 2(n + 1)H_n - 4n$$Using the harmonic number expansion $H_n = \sum_{m=1}^n \frac{1}{m} = \ln n + \gamma + O(1/n)$ and converting from natural log to base-2 log ($\ln n = \ln(2) \cdot \log_2 n \approx 0.69315 \log_2 n$):
$$\mathbb{E}[X] \approx 2n \ln n = (2 \ln 2)\, n \log_2 n \approx 1.3863\, n \log_2 n$$Notice how remarkably close this is to the information-theoretic optimum: Randomized Quicksort performs only $38.6\%$ more comparisons than Merge Sort ($1.0\, n \log_2 n$), and with Median-of-Three pivot selection, the constant drops further to $\frac{12}{7} \ln(2)\, n \log_2 n \approx 1.188\, n \log_2 n$!
Step through Bentley-McIlroy 3-way partition QuickSort, Bottom-Up MergeSort inversion counting, and non-comparison LSD RadixSort with live comparison and swap counters.
Invariant & State
| Pivot Strategy | Expected Comparisons ($\log_2 n$) | Expected Swaps (Hoare) | High-Probability Tail Bound |
|---|---|---|---|
| Uniform Random Pivot ($1$-sample) | $2 \ln(2)\, n \log_2 n \approx 1.386\, n \log_2 n$ | $\frac{1}{3} \ln(2)\, n \log_2 n \approx 0.231\, n \log_2 n$ | $\Pr[X > 4n \ln n] \le n^{-2}$ |
| Random Median-of-3 ($3$-sample) | $\frac{12}{7} \ln(2)\, n \log_2 n \approx 1.188\, n \log_2 n$ | $\frac{2}{7} \ln(2)\, n \log_2 n \approx 0.198\, n \log_2 n$ | $\Pr[T > c n \log n] \le n^{-c'}$ |
| Tukey's Ninther ($9$-sample) | $\approx 1.09\, n \log_2 n$ | $\approx 0.175\, n \log_2 n$ | Sub-exponential tail concentration |
| Merge Sort (Reference) | $1.000\, n \log_2 n - O(n)$ | $1.000\, n \log_2 n$ element moves | Deterministic $\le n \lceil \log_2 n \rceil$ |
Calling std::rand() % len inside a Quicksort recursion loop has two flaws: (1) 64-bit integer modulo (DIV) takes 20–40 cycles, and (2) rand() % len introduces modulo bias when len does not divide $2^{32}$. Production randomized algorithms pair a fast register-resident PRNG (such as SplitMix64 or xoshiro256**, ~2 cycles) with Daniel Lemire's Fast Range reduction: (uint64_t(rng32()) * uint64_t(len)) >> 32, mapping a 32-bit random word into $[0, len)$ in a single 3-cycle multiply-high instruction without division!
Production C++20 Implementation: Randomized Quicksort & Empirical $2(n+1)H_n - 4n$ Verifier
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <utility>
#include <vector>
struct SplitMix64 {
std::uint64_t state;
explicit constexpr SplitMix64(std::uint64_t seed = 0x9E3779B97F4A7C15ULL) noexcept : state(seed) {}
constexpr std::uint64_t next() noexcept {
std::uint64_t z = (state += 0x9E3779B97F4A7C15ULL);
z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9ULL;
z = (z ^ (z >> 27)) * 0x94D049BB133111EBULL;
return z ^ (z >> 31);
}
// Lemire's multiply-shift into [0, bound)
constexpr std::size_t uniform(std::size_t bound) noexcept {
return static_cast<std::size_t>((__uint128_t(next()) * __uint128_t(bound)) >> 64);
}
};
// Instrumented Randomized Quicksort counting exact key comparisons
template <typename T>
std::uint64_t randomized_quicksort_count(T* a, std::ptrdiff_t lo, std::ptrdiff_t hi, SplitMix64& rng) noexcept {
if (lo >= hi) return 0;
const std::ptrdiff_t len = hi - lo + 1;
const std::ptrdiff_t piv_idx = lo + static_cast<std::ptrdiff_t>(rng.uniform(static_cast<std::size_t>(len)));
std::swap(a[piv_idx], a[hi]);
const T pivot = a[hi];
std::uint64_t cmps = 0;
std::ptrdiff_t i = lo;
for (std::ptrdiff_t j = lo; j < hi; ++j) {
++cmps;
if (a[j] < pivot) {
std::swap(a[i++], a[j]);
}
}
std::swap(a[i], a[hi]);
cmps += randomized_quicksort_count(a, lo, i - 1, rng);
cmps += randomized_quicksort_count(a, i + 1, hi, rng);
return cmps;
}
// Exact theoretical expectation E[X] = 2(n + 1)*H_n - 4n for n distinct keys
inline double theoretical_expected_comparisons(std::size_t n) noexcept {
double h_n = 0.0;
for (std::size_t k = 1; k <= n; ++k) {
h_n += 1.0 / static_cast<double>(k);
}
return 2.0 * static_cast<double>(n + 1) * h_n - 4.0 * static_cast<double>(n);
}Randomized Quicksort is a Las Vegas randomized algorithm: its output is always 100% sorted, and only its running time is a random variable. While Chernoff bounds guarantee $\Pr[X > 4n \ln n] \le n^{-2}$, in safety-critical real-time systems or deterministic standard library APIs (where a global PRNG state cannot be mutated inside std::sort), David Musser's Introsort (1997) tracks recursion depth and deterministically switches to Heapsort if depth ever exceeds $2\lfloor\log_2 n\rfloor$, upgrading expected $O(n \log n)$ into strict worst-case $O(n \log n)$ with zero extra memory.