Skip to main content

Quicksort and Why Randomization Helps

What This Concept Is​

Quicksort partitions around a pivot and recursively sorts the regions outside its equal-key region. Partition interfaces differ: a pivot's final index, a boundary between regions, and a pair delimiting equal keys require different recursive calls. Copying recursion bounds between these interfaces can skip an element or fail to shrink the problem.

For distinct keys and a uniformly chosen pivot at each step, expected work is Theta(n log n). Worst-case work is Theta(n²). Randomness is over internal pivot choices for a fixed input; it is not a worst-case latency guarantee.

Why It Matters Here​

Partitioning is reusable in selection. It also makes assumptions visible: random pivots do not repair a partition that sends all equal keys to one side. A deterministic fallback can bound worst-case sorting work, while recursing on the smaller side and iterating over the larger bounds stack depth.

Concrete Examples​

A three-way partition maintains four half-open regions: [lo,lt) below pivot, [lt,i) equal, [i,gt) unknown, [gt,hi) above pivot. If a[i] is below, swap it with a[lt] and advance both indices. If above, decrement gt and swap with a[gt], leaving i unchanged because its new value is unexamined. If equal, advance i. The unknown length gt-i strictly decreases. On [2,1,2,3,2], the final regions have sizes 1,3,1. All-equal input needs only one linear partition and no further nontrivial recursive calls.

For distinct ranks i<j, they are compared in the usual random-pivot analysis only if an endpoint is the first pivot selected from ranks i through j. Probability is 2/(j-i+1). Summing these indicators gives 2(n+1)H_n-4n comparisons for the standard model. This expected count is not an instruction count or a speed ratio.

Common Confusion / Misconceptions​

Median-of-three is a heuristic, not a universal worst-case bound. A fixed seed is reproducible and predictable; it does not protect against an input chosen with knowledge of that seed. The random-pivot proof assumes input independent of the random choices. Two-way Lomuto can take quadratic time on all-equal keys even with random pivots. Ordinary in-place partitions are not stable.

How To Use It​

For a teaching implementation, write the partition contract and duplicate policy first. Use a local random generator so experiments can be reproduced. Recurse only on strict outer regions. Smaller-side recursion gives O(log n) stack space even if time remains quadratic. An introspective sort also limits partition depth and falls back to a worst-case O(n log n) method such as heapsort.

Check Yourself​

  1. Why is i unchanged after swapping from the right unknown region?
  2. Does a depth limit alone guarantee bounded work without a fallback?
  3. Which assumptions support the expected-comparison derivation?
  4. Why can a random pivot still fail badly on duplicate keys?

Mini Drill or Application​

Trace the four regions on [3,1,3,2,3]. Deliberately advance i after the right-side swap and find a failing fixture. Compare all-equal behavior of a two-way and three-way partition by counting scanned elements, not fabricated timings. Extend with a smaller-side-recursion proof. See P2.

Read This Only If Stuck​

Use CLRS, Skiena, or Sedgewick and Wayne for randomized quicksort, partition contracts, and duplicate keys. These links open book indexes; find the named topic in your edition. Use the reading guide for the bounded assignment and worked examples before adding another source.