Randomized Quick Sort Visual Guide | Draftsbook

Divide & Conquer · Article 11 of 62

Randomized Quick Sort

Pick the pivot uniformly at random. The expected runtime is O(n log n) on every input — no adversary can construct a bad case.

How it works

Plain Quick Sort hits O(n²) when the pivot consistently splits the array unevenly. With a fixed pivot policy (e.g., "always pick the last element"), an attacker — or just unlucky input like an already-sorted array — can guarantee that worst case.

Randomized Quick Sort eliminates that problem with one line of code: swap a random element in the current range to the pivot position before partitioning.

Choose a random index r ∈ [lo, hi].
Swap arr[r] with arr[hi].
Proceed with the normal Lomuto partition.

Each partition's expected balance is now over a uniformly random pivot, regardless of input. The result: expected O(n log n) runtime on every input, with a negligible probability of pathological recursion.

Complexity

Best time

O(n log n)

Average time

O(n log n)

Worst time

O(n²) — only with probability ≈ n!⁻¹

Extra space

O(log n) expected

Stable

In-place

Yes

Switching from "last element" pivot to "random element" is the single highest-leverage change you can make to a quicksort. Median-of-three improves things further but still needs randomization to be truly adversary-proof.

Interactive visualization

Pseudocode

procedure randomizedQuickSort(A, lo, hi):
  if lo < hi:
    r ← random integer in [lo, hi]
    swap A[r], A[hi]
    p ← partition(A, lo, hi)
    randomizedQuickSort(A, lo, p − 1)
    randomizedQuickSort(A, p + 1, hi)

JavaScript implementation

function randomizedQuickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo < hi) {
    const r = lo + Math.floor(Math.random() * (hi - lo + 1));
    [arr[r], arr[hi]] = [arr[hi], arr[r]];
    const p = partition(arr, lo, hi);
    randomizedQuickSort(arr, lo, p - 1);
    randomizedQuickSort(arr, p + 1, hi);
  }
  return arr;
}

function partition(arr, lo, hi) {
  const pivot = arr[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
  return i + 1;
}

Pros and cons

Pros

Expected O(n log n) on every input — no worst-case input exists.
Trivially small code change over plain Quick Sort.
Defeats adversarial attacks like algorithmic complexity DoS.
Preserves all of Quick Sort's practical advantages.

Cons

Still not stable.
Worst-case bound is unchanged in theory — only the expected case improves.
Requires a usable PRNG; in security-sensitive contexts you'd want a tamper-resistant source.

When to use it

Default Quick Sort implementation in almost every standard library.
User-supplied input where an attacker might construct worst-case data.
Database query engines sorting on indexed columns.

Up next: Three-Way Quick Sort — going from one pivot to two — partitioning into three regions for free, and reducing the recursion depth.

Randomized Quick Sort: Mechanism, Complexity Analysis & Interactive Visualizer