1. Quick Sort

Quick sort is the most widely used general-purpose in-memory sorting algorithm. Introduced by C. A. R. Hoare in 1959-1962 ¹², it selects a pivot element, partitions the array into elements smaller than the pivot and elements larger, and recursively sorts each partition. Its expected \(O(n \log n)\) cost combined with exceptional cache performance makes it roughly two to three times faster than merge sort in practice on modern hardware, despite an identical asymptotic average complexity.

1.1 Mathematical Foundation

1.1.1 Partitioning Invariant

After a Lomuto partition step on sub-array \(A[p..r]\) with pivot \(x = A[r]\):

Every element left of index \(q\) is \(\leq x\); every element right is \(\geq x\).

1.1.2 Recurrence and Expected Complexity

Let pivot rank \(k\) be uniform over \(\{0, 1, \ldots, n-1\}\). Then:

Taking expectation over \(k\):

Solving via substitution with \(\mathbb{E}[T(n)] \leq cn\ln n\):

The constant is approximately \(2n \ln n \approx 1.386\, n \log_2 n\) comparisons, which is larger than merge sort's \((n \log_2 n)\) theoretical minimum but offset by far lower memory traffic ²¹.

1.1.3 Worst Case

When the pivot is always the minimum or maximum (e.g. sorted or reverse-sorted input with a naive pivot selection), all \(n - 1\) elements fall on one side:

Randomised pivot selection makes this event have probability \(1/n!\) for any fixed input.

1.2 The Algorithm

1.2.1 Lomuto Partition

PARTITION(A, p, r):
  x = A[r]          // pivot is last element
  i = p - 1
  for j = p to r - 1:
    if A[j] ≤ x:
      i = i + 1
      swap A[i] and A[j]
  swap A[i + 1] and A[r]
  return i + 1       // final pivot index q

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

1.2.2 Randomised Pivot

RANDOMISED-PARTITION(A, p, r):
  i = RANDOM(p, r)
  swap A[i] and A[r]
  return PARTITION(A, p, r)

Randomly selecting the pivot before calling PARTITION transforms any fixed input pattern into one that behaves like a random permutation, eliminating the \(O(n^2)\) worst case with high probability ².

1.2.3 Hoare Partition (original)

Hoare's original scheme uses two inward-moving pointers and performs fewer swaps on average (one third as many as Lomuto):

HOARE-PARTITION(A, p, r):
  x = A[p]          // pivot is first element
  i = p - 1
  j = r + 1
  while true:
    repeat j = j - 1 until A[j] ≤ x
    repeat i = i + 1 until A[i] ≥ x
    if i < j: swap A[i] and A[j]
    else:     return j

1.3 Correctness: Loop Invariant in PARTITION (Lomuto)

At the start of each iteration with index \(j\):

1. All elements in \(A[p..i]\) satisfy \(A[k] \leq x\).
2. All elements in \(A[i+1..j-1]\) satisfy \(A[k] > x\).
3. \(A[r] = x\).

Each iteration either extends region 1 (when \(A[j] \leq x\), swap brings it into \(A[p..i]\)) or extends region 2 (when \(A[j] > x\), \(j\) advances).

1.4 Complexity

The \(O(\log n)\) stack depth comes from always recursing on the shorter partition first; if the longer partition is recursed first the stack depth can reach \(O(n)\).

1.5 Variants

1.5.1 Three-Way Partition (Dutch National Flag)

When there are many equal keys, the standard partition degenerates: all equal elements repeatedly end up in the same partition, degrading to \(O(n^2)\) on arrays with few distinct values. Dijkstra's Dutch National Flag partition splits the array into three regions:

Elements equal to the pivot are placed in the middle region and are already sorted; only the strictly smaller and strictly larger regions are recursed on. This achieves \(O(n)\) on arrays with \(O(1)\) distinct keys ¹.

1.5.2 Introsort

The C++ standard library std::sort uses introsort: quick sort until the recursion depth exceeds \(2 \lfloor \log_2 n \rfloor\), then switch to heap sort. This ensures \(O(n \log n)\) worst case while retaining quick sort's cache-friendly average-case performance.

1.5.3 Median-of-Three Pivot

Choose the pivot as the median of \(A[p]\), \(A[\lfloor (p+r)/2 \rfloor]\), and \(A[r]\). Eliminates worst-case behaviour on sorted and reverse-sorted input, at the cost of two extra comparisons per call.

1.6 Comparison with Merge Sort and Heap Sort

1.7 Interactive Demo

The animation shows Lomuto partition on a 16-element array with a highlighted pivot and two-pointer sweep. Press Step or Play to watch the partitioning.