☕ Buy me a coffee — $3

Quick Sort

Overview

Quick Sort is a divide-and-conquer sorting algorithm that picks a pivot element and partitions the array around the pivot. Elements smaller than the pivot are placed before it, and elements greater than the pivot are placed after it. This process is repeated recursively for the sub-arrays.

Quick Sort is one of the most widely used sorting algorithms due to its excellent average-case performance of O(n log n). However, it has a worst-case time complexity of O(n²), which occurs when the pivot is always the smallest or largest element.

Quicksort is not "just another O(n log n) sort." Despite the pessimistic worst case, it is faster than mergesort on real hardware for most inputs by a factor of two or three. The reason is entirely about memory access patterns: quicksort's partition step scans the array linearly from both ends toward the middle, which is exactly the pattern that modern CPU cache prefetchers are designed to accelerate. Every C++ standard library's std::sort, Rust's sort_unstable, and Go's sort.Sort are quicksort variants for precisely this reason.

History: Hoare and the Machine Translation Project

Quicksort was invented in 1959 by Tony Hoare, then a 25-year-old graduate student at Moscow State University working on a machine-translation project between Russian and English. The project needed to sort Russian words alphabetically so they could be looked up in a dictionary. Hoare tried mergesort first, but the machine he was using (a Ferranti Mercury) did not have enough memory for mergesort's auxiliary array. He designed quicksort specifically to work in-place, and published it in 1961 as "Algorithm 64: Quicksort" in the Communications of the ACM, a paper of about one page, containing the entire algorithm.

Hoare's original partition scheme (now called Hoare partitioning) uses two pointers moving toward each other and swaps elements found on the wrong side. Nico Lomuto's later partition scheme (the one shown above, and used in most modern textbooks) uses a single scan and is simpler to code correctly, but does more swaps than Hoare partitioning. On modern hardware Hoare's original scheme is often faster despite the more complex control flow, which is why production implementations frequently use it rather than Lomuto's version.

Hoare went on to invent formal program verification, receive the Turing Award in 1980, and become one of the most influential figures in computer science. He also famously admitted, in his 1980 Turing Award lecture, to having invented the null reference in 1965 and called it his "billion-dollar mistake." Quicksort is unambiguously his positive legacy.

Pivot Selection: Where Quicksort Actually Fails

The single most consequential decision in a quicksort implementation is how to choose the pivot. A bad pivot choice turns O(n log n) into O(n²); a good one keeps performance predictable.

First or last element. The simplest choice, and the one you should never use in production. If the input happens to be already sorted (or reverse sorted), this choice partitions the array into pieces of size 0 and n−1 at every level, O(n²) behaviour on precisely the input that most benchmarks hit first, because "already sorted" is a common real-world case. Early C library implementations of qsort using this scheme were slower on sorted input than on random input, which surprised many programmers.

Middle element. Better than first/last, and O(n log n) on already-sorted input, but still vulnerable to constructed adversarial inputs. A pattern of the form [1, 3, 5, ..., 2, 4, 6, ...] (odd numbers followed by even) yields a bad partition with middle-element pivots and is easily generated by a programmer testing edge cases.

Median-of-three. Take the median of the first, middle, and last elements. This is what Sedgewick recommended in 1978 and what many standard-library implementations use. It is very hard to construct an adversarial input against median-of-three, and it keeps expected performance close to optimal.

Random pivot. Choose the pivot uniformly at random from the current partition. This gives O(n log n) expected time regardless of input distribution, the adversarial input is defeated because the adversary cannot predict which element will be chosen. The randomness is only needed at pivot selection; the rest of the algorithm is deterministic. This is the theoretically cleanest choice and is used in some research implementations.

Introsort. The pragmatic industry solution, invented by David Musser in 1997. Run quicksort with median-of-three or similar, but monitor the recursion depth. If it exceeds 2 log2 n, switch to heap sort to guarantee the O(n log n) bound. This gives quicksort's speed on typical input and heap sort's worst-case guarantee on adversarial input. C++'s std::sort has used introsort since 1998; Rust and Go use variants of the same idea.

Pattern-defeating quicksort (pdqsort). Orson Peters's 2016 algorithm, now used by Rust's sort_unstable and by Boost's parallel sort. Pdqsort adds three tricks on top of introsort: it detects common patterns (already sorted, reverse sorted, few unique values) and handles them in linear time, it uses branchless partitioning that avoids CPU branch mispredictions on random data, and it switches to heapsort on pathological input like classic introsort. Pdqsort is faster than introsort on essentially every input class and is the current state-of-the-art for unstable in-place sorting.

Three-Way Partitioning for Duplicate-Heavy Data

Standard two-way partitioning (elements ≤ pivot on the left, > pivot on the right) has a serious weakness: on arrays with many duplicates of the pivot value, it wastes work by making many equal-to-pivot elements swap through the partition even though they all belong at the same position. In the pathological case, an array of all identical elements, two-way partitioning degenerates to O(n²).

The fix is three-way partitioning: split the array into three regions on each partition step, strictly less than pivot, equal to pivot, and strictly greater than pivot, and recurse only on the strictly-less and strictly-greater regions. Elements equal to the pivot are placed in their final positions during this partition step and never touched again. This is called the Dutch National Flag partition, after a problem Edsger Dijkstra posed in his book A Discipline of Programming: given an array of red, white, and blue balls, sort them into that order in a single pass.

Robert Sedgewick and Jon Bentley published the modern algorithm for combining three-way partitioning with quicksort in 1993 ("Fast Algorithms for Sorting and Searching Strings"), and their variant is what modern production quicksorts use when they detect that many partitions have duplicate-heavy pivots. On arrays with few distinct values, three-way quicksort is linear-time (each distinct value takes one partition pass to place), which is asymptotically better than any comparison sort's O(n log n).

How It Works

The algorithm follows these steps:

  1. Choose Pivot: Select an element from the array as the pivot
  2. Partition: Rearrange the array so that all elements less than the pivot come before it, and all elements greater come after it
  3. Recurse: Apply the same process recursively to the sub-arrays on both sides of the pivot

The pivot selection is crucial. Common strategies include choosing the first element, last element, middle element, or a random element. The partition step ensures that after partitioning, the pivot is in its final sorted position.

Algorithm


QuickSort(arr, low, high):
    if low < high:
        pivot_index = Partition(arr, low, high)
        QuickSort(arr, low, pivot_index - 1)
        QuickSort(arr, pivot_index + 1, high)

Partition(arr, low, high):
    pivot = arr[high]  # Choose last element as pivot
    i = low - 1
    
    for j = low to high - 1:
        if arr[j] <= pivot:
            i = i + 1
            swap arr[i] and arr[j]
    
    swap arr[i + 1] and arr[high]
    return i + 1

Implementation


def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    return quick_sort(left) + middle + quick_sort(right)

# In-place version
def quick_sort_inplace(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quick_sort_inplace(arr, low, pivot_index - 1)
        quick_sort_inplace(arr, pivot_index + 1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

Complexity Analysis

  • Time Complexity:
    • Best Case: O(n log n) - when pivot divides array evenly
    • Average Case: O(n log n) - expected performance
    • Worst Case: O(n²) - when pivot is always smallest/largest
  • Space Complexity: O(log n) for recursion stack (average case), O(n) worst case

The worst case occurs when the array is already sorted and we always pick the first or last element as pivot. This can be avoided by using randomized pivot selection or median-of-three pivot selection.

Characteristics

  • Stable: No - does not preserve relative order of equal elements
  • In-place: Yes (with in-place implementation) - can be done with O(log n) extra space
  • Adaptive: No, and in fact performance depends heavily on input order for any deterministic pivot rule. With last-element pivots, already-sorted input is the worst case. Randomizing the pivot removes the dependence on input order, which is precisely why it is standard.
  • Online: No - requires the entire array to be present

When to Use Quick Sort

Quick Sort is an excellent choice when:

  • Average-case performance is more important than worst-case guarantee
  • You need in-place sorting with good average performance
  • Stability is not required
  • You can use randomized pivot selection to avoid worst-case scenarios
  • General-purpose sorting where data distribution is unknown

Pivot Selection Strategies

  • First/Last Element: Simple but can lead to worst-case O(n²)
  • Middle Element: Better than first/last, but still can be problematic
  • Random Element: Reduces probability of worst-case, good for general use
  • Median-of-Three: Choose median of first, middle, and last elements - good balance in practice, but still deterministic and therefore still defeatable by a crafted input
  • Median-of-Medians: Guarantees a pivot in the middle 30–70% of the range in O(n), making the worst case O(n log n). The constants are poor enough that it is rarely used for sorting, though it is the basis of deterministic selection (quickselect).

Three Problems the Basic Version Has

The Lomuto partition above is the clearest to teach, but it has real weaknesses worth knowing before you use quicksort in anger.

1. Duplicate elements. On an array where every element is equal, Lomuto puts all of them on one side of the pivot, giving a maximally unbalanced split and O(n²) behaviour on what should be the easiest possible input. The fix is three-way partitioning (the Dutch national flag algorithm), which separates the array into < pivot, = pivot, and > pivot, and recurses only on the outer two. With many duplicates this turns O(n²) into O(n).

2. Swap count. Hoare's original partition scheme, which walks two pointers inward from both ends, performs roughly three times fewer swaps than Lomuto. It is fiddlier to get right, the returned index is not the pivot's final position, but it is what production implementations actually use.

3. Adversarial input. A deterministic pivot rule means an attacker who knows your implementation can construct input that forces O(n²). This is a genuine denial-of-service vector, and it has been exploited against real systems. Randomize the pivot, or use introsort.

What Production Sorts Actually Do: Introsort

No serious standard library ships bare quicksort. Introsort (Musser, 1997) resolves the quicksort/heapsort tension by combining three algorithms:

  1. Run quicksort, which is fast in the common case.
  2. Track recursion depth. If it exceeds ~2 log n, a signal that pivots are going badly, switch that subarray to heap sort, guaranteeing O(n log n).
  3. On subarrays below ~16 elements, stop recursing and finish with insertion sort, which wins at small sizes on cache behaviour and low overhead.

The result keeps quicksort's average-case speed while making the O(n²) worst case unreachable. This is what C++ std::sort does. Rust's sort_unstable and Go's sort (since 1.19) use pdqsort (pattern-defeating quicksort), a further refinement that adds three-way partitioning for duplicates and detects already-sorted runs.

Example

Sorting [10, 7, 8, 9, 1, 5] with pivot as last element: 

Initial: [10, 7, 8, 9, 1, 5]     pivot = arr[high] = 5

Lomuto partition, walking j from low to high-1 and swapping into position i+1
whenever arr[j] <= pivot:

  i=-1  j=0: 10 <= 5? no
        j=1:  7 <= 5? no
        j=2:  8 <= 5? no
        j=3:  9 <= 5? no
        j=4:  1 <= 5? YES -> i=0, swap arr[0],arr[4]  ->  [1, 7, 8, 9, 10, 5]
  finally swap arr[i+1] with the pivot: swap arr[1],arr[5]

  Result: [1, 5, 8, 9, 10, 7]     pivot 5 now at index 1, its final position
           ^^^   ^^^^^^^^^^^
          < 5      > 5  (unordered among themselves)

Recurse left on [1]              -> already sorted (single element)
Recurse right on [8, 9, 10, 7]   -> pivot = 7
  8<=7? no   9<=7? no   10<=7? no
  swap arr[i+1] with pivot       -> [7, 9, 10, 8]
  Recurse on [] and [9, 10, 8]   -> pivot = 8 -> [8, 10, 9] -> ... -> [8, 9, 10]

Final: [1, 5, 7, 8, 9, 10]

Note that partitioning does not sort the two sides, it only guarantees that everything left of the pivot is ≤ it and everything right is > it. The pivot itself is in its final position and is never moved again; that is the invariant the recursion relies on.

Related Algorithms

Explore other sorting algorithms: