Quick Sort Pivot Selection Strategies

How Quick Sort Works

Quick Sort is the most widely used general-purpose sorting algorithm in practice. It works by selecting a pivot element and partitioning the array so that all elements less than the pivot come before it and all elements greater come after it.

The Partition Scheme

The Lomuto partition scheme (used in many textbooks) works as follows:

function partition(arr, low, high):
  pivot = arr[high]  // last element as pivot
  i = low - 1
  for j = low to high - 1:
    if arr[j] < pivot:
      i++
      swap(arr[i], arr[j])
  swap(arr[i+1], arr[high])
  return i + 1

Pivot Selection Strategies

The choice of pivot dramatically affects Quick Sort's performance:

Strategy	Best Case	Worst Case	Notes
Last element	O(n log n)	O(n²)	Degrades on sorted input
First element	O(n log n)	O(n²)	Same problem as last element
Random	O(n log n) expected	O(n²) rare	Good practical choice
Median-of-three	O(n log n)	O(n²) very rare	Best practical choice

Median-of-Three

The median-of-three strategy picks the median of the first, middle, and last elements as the pivot. For the array [8, 2, 5, 1, 9]:

• First = 8, Middle = 5, Last = 9
• Median = 8
• This avoids the worst case on sorted and reverse-sorted input

Why Quick Sort Is Fast in Practice

Despite its O(n²) worst case, Quick Sort is usually faster than Merge Sort because:

1. Cache locality: Elements are compared and swapped within the same array region
2. No extra memory: In-place partitioning avoids allocation overhead
3. Small constant factor: The inner loop is tight — just a comparison and a conditional swap
4. Tail call optimization: The smaller partition can be processed with tail recursion

Introsort: Quick Sort in Production

Modern C++ and Rust standard libraries use introsort, which starts with Quick Sort but switches to Heap Sort if the recursion depth exceeds 2 * log n, guaranteeing O(n log n) worst-case performance while retaining Quick Sort's practical speed.