6.5 Quick Sort

Quick sort is a divide and conquer sorting algorithm based on partitioning. It chooses a pivot, rearranges the array so that smaller elements go to one side and larger elements go to the other side, and then recursively sorts the two partitions. Unlike merge sort, quick sort does most of its work before the recursive calls.

Problem

You have an array A[0..n-1]. You want an in-place sorting algorithm with strong average-case performance, low auxiliary memory usage, and good practical speed on arrays.

Solution

Choose a pivot value. Partition the array around that pivot. Then recursively sort the left and right partitions.

A common high-level form is:

quick_sort(A, lo, hi):
  if hi - lo <= 1:
    return

  p = partition(A, lo, hi)

  quick_sort(A, lo, p)
  quick_sort(A, p + 1, hi)

Here [lo, hi) is a half-open range. The pivot is placed into its final position p, all elements before p are less than or equal to it, and all elements after p are greater than or equal to it.

One simple partition procedure is the Lomuto partition scheme:

partition(A, lo, hi):
  pivot = A[hi - 1]
  i = lo

  for j = lo to hi - 2:
    if A[j] <= pivot:
      swap A[i] and A[j]
      i = i + 1

  swap A[i] and A[hi - 1]
  return i

This version uses the last element as the pivot. It is easy to understand, but it performs poorly on already sorted input unless the pivot choice is improved.

Example

Start with:

[5, 2, 4, 1, 3]

Choose the last element, 3, as the pivot. Scan from left to right. Elements less than or equal to 3 are moved to the front.

After scanning, the array becomes:

[2, 1, 3, 5, 4]

The pivot 3 is now in its final position. The left partition is:

[2, 1]

The right partition is:

[5, 4]

Quick sort then sorts each partition recursively. The final array is:

[1, 2, 3, 4, 5]

The pivot itself does not need to be moved again after partitioning. It is already in the position it will occupy in the final sorted array.

Partition Invariant

During Lomuto partitioning, before each iteration of the loop with index j, the range is divided into three parts:

A[lo..i-1]      contains elements <= pivot
A[i..j-1]       contains elements > pivot
A[j..hi-2]      has not been inspected
A[hi-1]         is the pivot

When A[j] <= pivot, the algorithm swaps A[j] with A[i] and increments i. This extends the first region by one element.

When A[j] > pivot, no swap is needed. The element remains in the second region, and the scan moves on.

After the loop finishes, every element before i is less than or equal to the pivot, and every element from i to hi-2 is greater than the pivot. Swapping the pivot into position i gives:

A[lo..i-1]      contains elements <= pivot
A[i]            is the pivot
A[i+1..hi-1]    contains elements > pivot

This proves that the pivot is in its final sorted position.

Correctness

Quick sort is correct by induction on the length of the range.

If the range has length 0 or 1, it is already sorted.

For a longer range, partitioning places the pivot into a position where every element on the left is less than or equal to it, and every element on the right is greater than or equal to it. The recursive calls sort the left and right ranges. Since all elements in the left range are less than or equal to the pivot, and all elements in the right range are greater than or equal to the pivot, combining the sorted left range, pivot, and sorted right range gives a sorted range.

The permutation condition holds because partitioning uses swaps only. Recursive calls also use swaps only. Therefore no element is created or removed.

Complexity

Quick sort is fast when partitions are reasonably balanced. If each pivot splits the array into two roughly equal parts, the recursion depth is logarithmic and each level performs linear partitioning work:

O(n log n)

The worst case occurs when each pivot is the smallest or largest element. Then one side has length 0 and the other has length n - 1. The recurrence becomes:

T(n) = T(n - 1) + O(n)

which gives:

O(n^2)

The auxiliary space depends on recursion depth. With balanced partitions, the stack uses:

O(log n)

In the worst case, it can use:

O(n)

A robust implementation reduces this risk by using randomized pivots, median-of-three pivots, or introspective sorting.

Pivot Selection

Pivot choice determines the shape of the recursion tree.

Using the last element is simple but fragile. Already sorted input produces worst-case behavior.

Using a random pivot makes adversarial order unlikely. Before partitioning, choose a random index in [lo, hi), swap it with hi - 1, and then use the same partition procedure.

randomized_partition(A, lo, hi):
  r = random integer in [lo, hi)
  swap A[r] and A[hi - 1]
  return partition(A, lo, hi)

Median-of-three pivoting chooses the median of the first, middle, and last elements. This reduces the chance of very poor splits on already sorted or reverse sorted arrays, while avoiding the cost of full randomization.

Stability

Standard quick sort is not stable. Partitioning swaps elements across the array, and equal keys may change relative order.

For example:

[(2, A), (1, B), (2, C)]

Depending on pivot choice and swaps, the final result may place (2, C) before (2, A). The array is sorted by key, but stability is lost.

Stable quick sort variants exist, but they usually require extra memory or more complex partitioning. When stability is required, merge sort is often a better default.

Three-Way Partitioning

When the input contains many duplicate keys, ordinary two-way partitioning can waste work by repeatedly sorting elements equal to the pivot. Three-way partitioning divides the range into:

elements < pivot
elements = pivot
elements > pivot

A common form is the Dutch national flag partition:

three_way_quick_sort(A, lo, hi):
  if hi - lo <= 1:
    return

  pivot = A[lo]
  lt = lo
  i = lo
  gt = hi

  while i < gt:
    if A[i] < pivot:
      swap A[lt] and A[i]
      lt = lt + 1
      i = i + 1
    else if A[i] > pivot:
      gt = gt - 1
      swap A[i] and A[gt]
    else:
      i = i + 1

  three_way_quick_sort(A, lo, lt)
  three_way_quick_sort(A, gt, hi)

This version does not recursively sort the middle region because every element there is equal to the pivot. It can be much faster on arrays with many duplicates.

Implementation Notes

Quick sort is a strong default for in-memory arrays when stability is not required. It has good cache behavior because partitioning scans contiguous memory. It also avoids the linear auxiliary buffer required by standard merge sort.

Production implementations usually include safeguards:

randomized or median-of-three pivot selection
switch to insertion sort for small ranges
tail-recursion elimination
recursion-depth limit
fallback to heap sort when depth is too large

The last combination is known as introsort. It keeps quick sort’s speed in common cases while avoiding quadratic worst-case behavior.

Common Bugs

A common bug is recursing on ranges that still include the pivot. If partition returns the final pivot index p, the recursive calls should exclude p.

Another common bug is mixing closed intervals and half-open intervals. Choose one convention and use it everywhere.

Partition code is also prone to infinite loops when equal elements are handled incorrectly. Three-way partitioning is often safer when duplicates are frequent.

A performance bug appears when the last element is always used as the pivot on sorted input. The code remains correct, but the runtime degrades to quadratic.