Randomized Algorithms7 min read

Randomized Quick Sort

A random pivot destroys adversarial worst-case inputs
expected:Fast · \(O(n \log n)\)worst case:Extremely unlikely · \(O(n^2)\)space:\(O(\log n)\) expected

Imagine you need to sort 100 people by height. You pick someone from the group to be the referee. Everyone shorter stands to their left, everyone taller stands to their right. Then you do the same thing recursively for each half.

If the referee happens to be near the middle height-wise, each half has about 50 people — and the work halves nicely at each step: \(O(n \log n)\) total. But if you always pick the tallest person as referee, one side has 99 people and the other has 0 — degenerate \(O(n^2)\) behavior.

The fix is simple: pick the referee randomly. A random person is unlikely to be the very tallest or shortest. And even if one unlucky pick happens, the next level of recursion gets a new random choice — the chances of every single pick being terrible shrink exponentially.

Why Deterministic QuickSort Fails on Sorted Input

The classic bug in deterministic QuickSort: pick the last element as pivot every time. On an already-sorted array like [1, 2, 3, 4, 5], the last element is always the maximum. Every partition is maximally unbalanced: one side has 0 elements, the other has n-1. You get n recursion levels, each doing \(O(n)\) work — quadratic total.

This isn't just a theoretical problem. Sorting a sorted or nearly-sorted list is a very common real-world operation. Many systems feed sorted data into QuickSort and wonder why it crawls.

Random Pivot: No Input Can Be Adversarial

With a random pivot, no fixed input causes worst-case behavior. To force \(O(n^2)\), the adversary would need to predict your random choices at every single level of recursion — which they can't do. The worst case becomes a function of your random number generator, not the data.

The Expected Comparisons Analysis

Define X_{ij} = 1 if elements with sorted ranks i and j are ever directly compared. Two elements are compared only when one of them is the pivot while both are in the same subarray. The probability of this? Exactly 2 / (j − i + 1) — there are j-i+1 elements between them in sorted order, and the comparison happens only if i or j is picked first as pivot.

Summing over all pairs: E[comparisons] = Σ 2/(j-i+1) ≈ 2n·ln(n) = \(O(n \log n)\). This holds for every possible input.

Introsort: The Best of Both Worlds

Real-world sort implementations (C++ std::sort, Rust's sort_unstable) use introsort: start with randomized QuickSort but monitor recursion depth. If depth exceeds 2·log n — a sign of consistently bad pivots — switch to HeapSort, which guarantees \(O(n \log n)\) worst case. This combines QuickSort's excellent cache performance with an absolute worst-case guarantee. Randomized QuickSort is a classic Las Vegas algorithm — always correct, only runtime varies.

Note: The probability that Randomized QuickSort takes significantly longer than \(O(n \log n)\) on any input decreases faster than 1/n^c for any constant c. In practice, you'd sooner win the lottery three times in a row than hit \(O(n^2)\) behavior.

Randomized QuickSort

import random


def quicksort(arr, lo, hi):
    if lo >= hi:
        return
    # Random pivot selection
    pivot_idx = random.randint(lo, hi)
    arr[pivot_idx], arr[hi] = arr[hi], arr[pivot_idx]
    pivot = arr[hi]


    # Partition
    p = lo
    for i in range(lo, hi):
        if arr[i] <= pivot:
            arr[p], arr[i] = arr[i], arr[p]
            p += 1
    arr[p], arr[hi] = arr[hi], arr[p]


    quicksort(arr, lo, p - 1)
    quicksort(arr, p + 1, hi)


# Test on sorted input — the classic worst case for deterministic QS
arr = list(range(10))  # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
quicksort(arr, 0, len(arr) - 1)
print(arr)


# Test on random input
arr2 = [5, 2, 8, 1, 9, 3]
quicksort(arr2, 0, len(arr2) - 1)
print(arr2)
Output
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 5, 8, 9]

Complexity

🚀 Expected timeHolds for every possible input permutation — not just random inputs
Fast for every input\(O(n \log n)\)
💀 Worst-case timeRequires the random number generator to choose the worst pivot on every single recursive call
Astronomically unlikely\(O(n^2)\)
🌟 Best-case timeWhen every pivot perfectly splits the subarray — coincides with expected
Perfect splits every time\(O(n \log n)\)
📚 Space (call stack)Expected recursion depth; \(O(n)\) in worst case — use tail recursion on smaller partition to be safe
Shallow recursion on average\(O(\log n)\)

Quick check

Why does deterministic QuickSort (last-element pivot) perform worst on sorted input?

Continue reading

Quick Sort
Pick a pivot, split the crowd — everyone shorter left, taller right
→
Las Vegas vs Monte Carlo
Correct-always vs probably-correct — two flavors of randomized algorithms
→
QuickSelect
Find the kth smallest without fully sorting
→