Quicksort: A Complete Guide to Description, Performance, and Randomization

The Divide-and-Conquer Structure of Quicksort

Quicksort follows the divide-and-conquer paradigm introduced earlier in this series, but with a distinctive twist: unlike merge sort, which does equal work dividing and combining, quicksort does all of its real work during the divide step, and the combine step is trivial.

QUICKSORT(A, p, r):
  if p < r:
      q = PARTITION(A, p, r)
      QUICKSORT(A, p, q - 1)
      QUICKSORT(A, q + 1, r)

The algorithm's entire logic rests on the PARTITION procedure, which rearranges the subarray A[p..r] around a chosen Pivot element, such that every element to the pivot's left is less than or equal to it, and every element to its right is greater than or equal to it. Once partitioned, the two resulting subarrays are recursively sorted independently, and since the pivot is already in its final sorted position, no explicit combine step is needed.

The Partition Procedure in Detail

The classic Lomuto partition scheme selects the last element of the subarray as the pivot and maintains an invariant as it scans through the array.

PARTITION(A, p, r):
  x = A[r]           // pivot
  i = p - 1
  for j = p to r - 1:
      if A[j] ≤ x:
          i = i + 1
          exchange A[i] with A[j]
  exchange A[i + 1] with A[r]
  return i + 1

Tracing through an example makes this concrete. Consider partitioning [2, 8, 7, 1, 3, 5, 6, 4] with pivot value 4 (the last element).

Initial: [2, 8, 7, 1, 3, 5, 6, 4]   pivot = 4, i = -1 (using 0-index p=0)

j=0: A[0]=2 ≤ 4 → i=0, swap A[0],A[0]: [2, 8, 7, 1, 3, 5, 6, 4]
j=1: A[1]=8 > 4 → no action
j=2: A[2]=7 > 4 → no action
j=3: A[3]=1 ≤ 4 → i=1, swap A[1],A[3]: [2, 1, 7, 8, 3, 5, 6, 4]
j=4: A[4]=3 ≤ 4 → i=2, swap A[2],A[4]: [2, 1, 3, 8, 7, 5, 6, 4]
j=5: A[5]=5 > 4 → no action
j=6: A[6]=6 > 4 → no action

Final swap: exchange A[3] with A[7]: [2, 1, 3, 4, 7, 5, 6, 8]
Return q = 3 — pivot 4 is now in its final position

After partitioning, elements [2, 1, 3] to the left are all ≤ 4, and elements [7, 5, 6, 8] to the right are all ≥ 4, with the pivot itself correctly positioned at index 3. This procedure runs in Θ(n) time for a subarray of size n, since it performs a single pass through the array.

The Worst Case: Already-Sorted or Reverse-Sorted Input

Quicksort's performance depends entirely on how balanced the partitions are. The worst case occurs when the partition is maximally unbalanced — one subarray of size n-1 and one of size 0 — which happens, using the Lomuto scheme above, whenever the input array is already sorted or reverse-sorted.

Worst-case recurrence: T(n) = T(n-1) + T(0) + Θ(n)
                              = T(n-1) + Θ(n)

Solving this recurrence (an arithmetic series):
T(n) = Θ(n) + Θ(n-1) + ... + Θ(1) = Θ(n²)

This Θ(n²) worst case is a genuine practical concern: naively implemented quicksort performs disastrously on already-sorted data, a scenario that occurs disturbingly often with real-world data, such as log files or pre-processed input.

The Best Case: Perfectly Balanced Partitions

At the opposite extreme, if the partition always splits the array into two equal halves, the recurrence becomes identical in structure to merge sort's:

Best-case recurrence: T(n) = 2T(n/2) + Θ(n)

Using the master method covered earlier in this series:
T(n) = Θ(n log n)

A Crucial Insight: Balanced Splits Are More Common Than Expected

A key insight makes quicksort's average behavior far better than the pessimistic worst case might suggest: even a consistently unbalanced split, such as a 9-to-1 ratio at every level, still produces Θ(n log n) running time overall, since the recursion depth remains logarithmic and the per-level work remains linear. Only splits that are unbalanced by a constant amount at every single level, such as always splitting off just one element, produce the true quadratic worst case.

Randomized Quicksort: Protecting Against the Worst Case

Since deterministic quicksort's worst case is triggered by specific, predictable input orderings, a simple but powerful fix exists: choose the pivot randomly rather than deterministically picking the last element.

RANDOMIZED-PARTITION(A, p, r):
  i = RANDOM(p, r)
  exchange A[r] with A[i]
  return PARTITION(A, p, r)

RANDOMIZED-QUICKSORT(A, p, r):
  if p < r:
      q = RANDOMIZED-PARTITION(A, p, r)
      RANDOMIZED-QUICKSORT(A, p, q - 1)
      RANDOMIZED-QUICKSORT(A, q + 1, r)

This change guarantees that no specific input, chosen by an adversary or arising naturally, can reliably trigger the worst case, since the pivot choice is randomized independently of the input's order. The expected running time becomes O(n log n) for every input, connecting directly to the probabilistic analysis techniques discussed earlier in this series.

Analyzing the Expected Running Time Using Indicator Variables

The expected running time of randomized quicksort can be derived rigorously using the indicator random variable technique introduced earlier in this series. The key insight is that the total running time is dominated by the number of comparisons performed, and two elements are compared at most once, exactly when one of them is chosen as a pivot while the other is still in the same subarray.

Let Xij = indicator that elements zi and zj
         (the i-th and j-th smallest elements) are ever compared

The expected total number of comparisons is:
E[X] = Σ Σ (i

This confirms rigorously that randomized quicksort achieves O(n log n) expected running time on any input, using the same indicator variable and harmonic series techniques that proved useful for the hiring problem discussed earlier in this series.

Why Quicksort Remains Popular Despite Its Worst Case

Despite merge sort and heapsort, both discussed elsewhere in this series, offering guaranteed Θ(n log n) worst-case performance, quicksort remains extremely popular in practice for several reasons: its constant factors are typically smaller than merge sort's, it sorts in place unlike merge sort, and its access pattern exhibits excellent cache locality, discussed earlier in this series in the context of computer architecture, since the partition step scans memory sequentially. Randomization removes the practical risk of the worst case, making randomized quicksort the standard choice in most real-world sorting library implementations.