Comparison sorts II: quicksort, partition, and the production hybrids

Hoare's 1961 publication of Algorithm 64 in Communications of the ACM gave the world six lines of pseudocode and one sentence in plain English: pick a pivot, rearrange so smaller elements sit to its left and larger elements sit to its right, recurse on each half. Six lines. Sixty-five years later, the C standard library function is still named qsort, the C++ std::sort is still built on Hoare's primitive, and Java's primitive-array sort is a dual-pivot variant. The skeleton aged because the partition step is genuinely cheap: one O(n) pass per recursion level, no merge afterward, no auxiliary buffer. On random input, quicksort's constant factor beats every other comparison sort.

The catch is that the same six lines have a Theta(n^2) worst case.^[1] Hand a textbook quicksort an already-sorted array with a last-element pivot and it walks down a linear recursion chain, partitioning into a one-element-and-the-rest split at every level. The pathology was so corrosive in production that Tim Peters wrote Timsort in 2002 to replace CPython's sort,^[2] David Musser proposed introsort in 1997 to fix C++'s,^[3] and the Java team adopted Vladimir Yaroslavskiy's dual-pivot scheme in JDK 7. This chapter teaches both halves: the algorithm itself and the production-grade scaffolding that wraps around it.

The chapter pair builds toward a single sentence you should be able to recite from memory. Merge sort is stable, has guaranteed O(n log n) worst-case, but allocates O(n) auxiliary storage; quicksort is not stable, has expected O(n log n), but sorts in place. That sentence is the answer to "why merge sort here, not quicksort?" and it is what every interviewer wants when they push back on your choice.

Algorithm A: quicksort with median-of-three Lomuto partition#

The clearest way to teach quicksort is to lead with the partition step, because everything else is recursion you already know. Start with a six-element array and a target pivot value of 6:

arr = [5, 2, 4, 1, 3, 6]
pivot = 6 (the rightmost element)

After partition, every element less than or equal to 6 sits in the prefix and every element greater than 6 sits in the suffix. The pivot lands in its final sorted position. One pass, two indices.

The version called Lomuto partition (CLRS calls it just PARTITION) reads off the page in seven lines.^[4] Two indices: i is the boundary of the "less than or equal to pivot" prefix; j scans every position from lo to hi - 1. When arr[j] <= pivot, the algorithm advances i and swaps arr[i] with arr[j], extending the prefix by one cell. When arr[j] > pivot, the algorithm does nothing; the cell stays in the "greater than pivot" middle zone that grows alongside j. After the scan, one final swap places the pivot at index i + 1, sandwiched between the two bands.

The loop invariant is what makes the algorithm correct: at every iteration, arr[lo..i] holds elements <= pivot, arr[i+1..j-1] holds elements > pivot, and arr[j..hi-1] is unexamined. Initialize i = lo - 1 so the prefix starts empty; iterate j over the range; and the invariant survives every step.

Static fallback: a 16-step animation of the Lomuto sweep on [5, 2, 4, 1, 3, 6] showing i and j advance, the prefix grow, and the pivot land at index 5.

Why the obvious version explodes on sorted input#

Drop the textbook PARTITION procedure into the recursive shell and you get this:

# Brute force: works, but blows up on sorted input.
def quicksort_naive(arr, lo, hi):
    if lo >= hi:
        return
    pivot = arr[hi]                          # last element, no thought given
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
    p = i + 1
    quicksort_naive(arr, lo, p - 1)
    quicksort_naive(arr, p + 1, hi)

Submit this to LC 912 and the hidden 50,000-element sorted-input test times out. The reason is mechanical. With pivot = arr[hi] on a sorted array, every comparison arr[j] <= pivot succeeds (the pivot is the array's maximum), so i advances every iteration and ends at hi - 1. Partition returns hi. The next recursion processes arr[lo..hi-1], an n - 1 size sub-range, and the pattern repeats. Recursion depth becomes n. Total work becomes the recurrence T(n) = T(n - 1) + Theta(n), which solves to Theta(n^2). CLRS exercise 7.2-3 names this trigger explicitly: "the array A contains distinct elements and is sorted in decreasing order"; the same blowup happens on ascending-sorted input under last-element-pivot Lomuto.^[4:1] Reverse-sorted input is even worse: the partition does n - 1 swaps per level on top of the linear recursion.

The fix is to stop letting the input choose the pivot. Two options work and both are correctness fixes, not optimizations. CLRS's RANDOMIZED-PARTITION swaps arr[hi] with arr[random(lo, hi)] before partitioning; expected running time becomes Theta(n log n) regardless of input order, because the adversary can't pick worst-case input without seeing the random coins.^[4:2] Sedgewick's median-of-three is the deterministic alternative: sample arr[lo], arr[mid], and arr[hi], and place their median into arr[hi] before partition.^[5] Both choices turn the sorted-input pathology into an event no realistic input can trigger; median-of-three has a marginally better constant factor (expected comparisons drop from about 1.39 n log_2 n to 1.19 n log_2 n at the cost of three extra comparisons per partition) and is what the chapter teaches as the canonical reference.

The teaching reference#

# LC 912. Sort an Array
# Quicksort with median-of-three Lomuto partition.
from typing import List


def sort_array(nums: List[int]) -> List[int]:
    """LC 912: sort and return a new list. Input is not mutated."""
    arr = list(nums)
    if len(arr) > 1:
        _quicksort(arr, 0, len(arr) - 1)
    return arr


def _quicksort(arr: List[int], lo: int, hi: int) -> None:
    """In-place quicksort on arr[lo..hi] inclusive."""
    while lo < hi:
        # Median-of-three: place median(arr[lo], arr[mid], arr[hi]) into arr[hi].
        mid = lo + (hi - lo) // 2
        if arr[mid] < arr[lo]:
            arr[lo], arr[mid] = arr[mid], arr[lo]
        if arr[hi] < arr[lo]:
            arr[lo], arr[hi] = arr[hi], arr[lo]
        if arr[mid] < arr[hi]:
            arr[mid], arr[hi] = arr[hi], arr[mid]
        # arr[hi] now holds the median of the three; use it as Lomuto pivot.
        p = _lomuto_partition(arr, lo, hi)
        # Recurse on the smaller side; loop on the larger (Sedgewick tail-call fix).
        if p - lo < hi - p:
            _quicksort(arr, lo, p - 1)
            lo = p + 1
        else:
            _quicksort(arr, p + 1, hi)
            hi = p - 1


def _lomuto_partition(arr: List[int], lo: int, hi: int) -> int:
    """CLRS 4th ed. PARTITION: pivot is arr[hi]. Returns final pivot index."""
    pivot = arr[hi]
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
    return i + 1

// LC 912. Sort an Array
// Quicksort with median-of-three Lomuto partition.
public class Sol {
    public int[] sortArray(int[] nums) {
        int[] arr = nums.clone();
        if (arr.length > 1) {
            quicksort(arr, 0, arr.length - 1);
        }
        return arr;
    }

    private static void quicksort(int[] arr, int lo, int hi) {
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;     // overflow-safe vs. (lo + hi) / 2
            if (arr[mid] < arr[lo]) swap(arr, lo, mid);
            if (arr[hi]  < arr[lo]) swap(arr, lo, hi);
            if (arr[mid] < arr[hi]) swap(arr, mid, hi);
            int p = lomutoPartition(arr, lo, hi);
            if (p - lo < hi - p) {
                quicksort(arr, lo, p - 1);
                lo = p + 1;
            } else {
                quicksort(arr, p + 1, hi);
                hi = p - 1;
            }
        }
    }

    private static int lomutoPartition(int[] arr, int lo, int hi) {
        int pivot = arr[hi];
        int i = lo - 1;
        for (int j = lo; j < hi; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, hi);
        return i + 1;
    }

    private static void swap(int[] arr, int a, int b) {
        int t = arr[a]; arr[a] = arr[b]; arr[b] = t;
    }
}

// LC 912. Sort an Array
// Quicksort with median-of-three Lomuto partition.
#include <utility>
#include <vector>

class Solution {
public:
    std::vector<int> sortArray(std::vector<int>& nums) {
        std::vector<int> arr = nums;
        if (arr.size() > 1) {
            quicksort(arr, 0, static_cast<int>(arr.size()) - 1);
        }
        return arr;
    }

private:
    static void quicksort(std::vector<int>& arr, int lo, int hi) {
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] < arr[lo]) std::swap(arr[lo],  arr[mid]);
            if (arr[hi]  < arr[lo]) std::swap(arr[lo],  arr[hi]);
            if (arr[mid] < arr[hi]) std::swap(arr[mid], arr[hi]);
            int p = lomutoPartition(arr, lo, hi);
            if (p - lo < hi - p) {
                quicksort(arr, lo, p - 1);
                lo = p + 1;
            } else {
                quicksort(arr, p + 1, hi);
                hi = p - 1;
            }
        }
    }

    static int lomutoPartition(std::vector<int>& arr, int lo, int hi) {
        int pivot = arr[hi];
        int i = lo - 1;
        for (int j = lo; j < hi; ++j) {
            if (arr[j] <= pivot) {
                ++i;
                std::swap(arr[i], arr[j]);
            }
        }
        std::swap(arr[i + 1], arr[hi]);
        return i + 1;
    }
};

// LC 912. Sort an Array
// Quicksort with median-of-three Lomuto partition.
package main

func sortArray(nums []int) []int {
	arr := append([]int(nil), nums...)
	if len(arr) > 1 {
		quicksort(arr, 0, len(arr)-1)
	}
	return arr
}

func quicksort(arr []int, lo, hi int) {
	for lo < hi {
		mid := lo + (hi-lo)/2
		if arr[mid] < arr[lo] {
			arr[lo], arr[mid] = arr[mid], arr[lo]
		}
		if arr[hi] < arr[lo] {
			arr[lo], arr[hi] = arr[hi], arr[lo]
		}
		if arr[mid] < arr[hi] {
			arr[mid], arr[hi] = arr[hi], arr[mid]
		}
		p := lomutoPartition(arr, lo, hi)
		if p-lo < hi-p {
			quicksort(arr, lo, p-1)
			lo = p + 1
		} else {
			quicksort(arr, p+1, hi)
			hi = p - 1
		}
	}
}

func lomutoPartition(arr []int, lo, hi int) int {
	pivot := arr[hi]
	i := lo - 1
	for j := lo; j < hi; j++ {
		if arr[j] <= pivot {
			i++
			arr[i], arr[j] = arr[j], arr[i]
		}
	}
	arr[i+1], arr[hi] = arr[hi], arr[i+1]
	return i + 1
}

Three details earn their lines. None is optional, and skipping any one of them ships a real bug.

mid = lo + (hi - lo) // 2 dodges the integer overflow Joshua Bloch documented in 2006 in java.util.Arrays.binarySearch, where the bug had lain undetected for nine years.^[6] On signed 32-bit arithmetic, lo + hi overflows once the array exceeds 2^30 elements, the division stays negative, and the recursion runs off the end. The two forms are equivalent on unbounded integers; they are not equivalent on bounded integer types. Use the safe form by reflex.

Sedgewick's tail-call elimination — recurse on the smaller side, loop on the larger — bounds the recursion stack at O(log n) even in the worst case. Naive recursive quicksort uses O(n) stack frames on adversarial input; Python raises RecursionError at depth 1000, Java throws StackOverflowError somewhere between depth 2,000 and 10,000 depending on per-frame size. The while lo < hi loop with the smaller-side-first idiom processes the larger sub-range without consuming a frame, keeping stack depth proportional to the log of the input even when partition behaves badly. Skip the idiom and a 50,000-element worst-case input crashes rather than times out, which is harder to debug.

Median-of-three places the pivot at arr[hi], not at arr[mid]. This is a Lomuto-specific contract: _lomuto_partition reads its pivot from arr[hi] by definition. The three-comparison header sorts (arr[lo], arr[mid], arr[hi]) so arr[hi] ends up holding the median. Do it differently and the partition's invariant is wrong from the first scan.

The four implementations share one Lomuto-with-median-of-three skeleton; the only language-specific concession is the defensive copy at the top so the function does not mutate the caller's buffer. All four pass the eight-case canonical test, including the sorted-input case [1, 2, 3, 4, 5] and reverse-sorted [5, 4, 3, 2, 1] that would trigger Theta(n^2) under naive last-element-pivot Lomuto.

Worked example: median-of-three Lomuto on [5, 2, 4, 7, 1, 3, 2, 6]#

The canonical input is the same eight elements that panel-a of the widget animates under merge sort, so scrubbing both panels side by side surfaces the structural contrast: merge sort decomposes top-down then merges back up; quicksort partitions in place and recurses without a merge.

The first partition picks median-of-three of (arr[0]=5, arr[3]=7, arr[7]=6) = 6, swaps the median into arr[7], and runs Lomuto. Pivot 6 lands at index 6; the left band [5, 2, 4, 1, 3, 2] is everything <= 6; the right band is just [7]. Recursion descends three levels deep with pivots 4, 2, and 1 chosen at the next three subproblems. The duplicate 2s travel together through depth 2; median-of-three of (2, 2, 3) picks 2 as pivot, and the partition lands the second 2 adjacent to the first. Quicksort is not stable: their relative order in the output may differ from the input.

Static fallback: a 22-step trace of the median-of-three Lomuto algorithm on [5, 2, 4, 7, 1, 3, 2, 6] ending at [1, 2, 2, 3, 4, 5, 6, 7], with the recursion-tree depth visible at every partition.

The widget exposes two presets the chapter specifically wants you to compare. The "sorted input + naive last-pivot Lomuto" preset runs textbook PARTITION on [1, 2, 3, 4, 5, 6, 7, 8] and ships a 36-step trace as the algorithm walks a degenerate seven-deep linear recursion. The "sorted input + median-of-three" preset on the same array completes in 22 steps. Switching presets makes the quadratic blowup visible in step counts: same data, same algorithm shell, same partition scheme. Only the pivot rule changes, and Theta(n^2) becomes Theta(n log n).

Algorithm B: the production hybrids#

The textbook algorithm is not what your standard library ships. Five years after Hoare's paper, Bentley and McIlroy's 1993 Engineering a Sort Function documented the practical patches the BSD qsort lineage needed to survive production: median-of-three for medium subarrays, ninther (median of three medians of three) for large ones, three-way "fat partition" for arrays with equal keys, insertion-sort cutoff for small subarrays.^[7] Those four ideas plus one fallback are what every modern standard library is.

Introsort: quicksort with a heap-sort safety net#

David Musser's 1997 introsort is the algorithm the C++ STL ships as std::sort in libstdc++ and libc++.^[3:1] It runs median-of-three quicksort, but tracks recursion depth as it descends; if depth exceeds 2 log_2 n, the algorithm aborts the recursive call and runs heap sort on the remaining sub-range. The hybrid combines quicksort's average-case constant factor with heap sort's worst-case guarantee, yielding Theta(n log n) time on every input with quicksort-typical constants. Introsort is the production answer to "why does C++'s std::sort guarantee O(n log n) when quicksort doesn't?" The answer is: it is not quicksort.

Heap sort is the right fallback because it is Theta(n log n) worst-case, in-place (O(1) auxiliary space), and indifferent to input order. The cache behavior is worse than quicksort's, which is exactly why introsort uses it as a backstop rather than a default. Most calls never hit the depth threshold; the few that would have gone quadratic get rescued by heap sort instead. The next chapter, Heap sort and the n log n lower bound, proves the bound and shows heap sort's mechanics.

Timsort: stable, adaptive, the world's most-used comparison sort#

In 2002 Tim Peters wrote a sort routine for CPython that has since become the most-deployed comparison sort in the world. Timsort ships in Python's list.sort() and sorted(), in Java's Arrays.sort(Object[]) since Java 7 (2011), and in Android Java since 2009.^[2:1] The algorithm identifies natural runs in the input (maximal already-sorted subsequences), extends short runs to a minimum length using insertion sort, and merges runs from a stack under invariants on run-length ratios that bound worst-case merge cost. Theta(n log n) worst case, Theta(n) best case on already-sorted input, and stable.

The Tim Peters design notes for Timsort still live in the CPython source at Objects/listsort.txt, and they are worth reading once if you want to see what production sort engineers actually argue about.^[2:2] The relevant excerpt: "It has supernatural performance on many kinds of partially ordered arrays (less than lg(N!) comparisons needed, and as few as N-1), yet as fast as Python's previous highly tuned samplesort hybrid on random arrays." The win comes from real-world data being almost always partially ordered. Log files with batched out-of-order arrivals; commit lists assembled from multiple feeds; news article timestamps; spreadsheet imports. Worst-case-uniform inputs are an academic fiction; partially-sorted inputs are what production code actually sees.

In 2015, Stijn de Gouw and colleagues used the KeY theorem prover to verify Timsort's run-merging logic and discovered that Java's port carried a subtle bug in merge_collapse that could overflow the pending-runs stack on a contrived input.^[8] The Java team fixed the implementation in OpenJDK 8u80; CPython kept the original because no plausible machine could hold an array large enough to trigger the bug. The lesson is the chapter's running theme. Production-grade sort routines are not an excuse to ignore complexity; they are the result of a generation of engineers refusing to ignore complexity.

Dual-pivot quicksort: Java's primitive-array sort#

Vladimir Yaroslavskiy's 2009 dual-pivot quicksort is what Arrays.sort(int[]) (and the long[], double[], ... primitive overloads) ship in Java 7+.^[9] The algorithm picks two pivots p1 <= p2, partitions the array into three bands [< p1, p1..p2, > p2], and recurses on each. The performance benefit is cache-driven: three roughly-equal sub-ranges fit modern CPU cache hierarchies better than one pivot's two sub-ranges, yielding about a 10% lower constant factor than single-pivot quicksort on random integer arrays. Go's standard library went the same direction with pdqsort (pattern-defeating quicksort) for slices.Sort.

Picking between merge sort and quicksort#

The library-design rule of thumb that follows from the trade-off is mergesort for objects, quicksort for primitives. Objects carry secondary keys that may be observable, so stability matters; primitives are values without distinguishable copies, so stability is irrelevant. Java 7+ makes this split explicit in its standard library:

C++ chooses differently: std::sort is introsort (unstable, cache-locality optimized), and stability is opt-in via std::stable_sort (typically merge sort or block sort). Go's slices.Sort is pdqsort (unstable); stability is opt-in via slices.SortStableFunc. Python's list.sort is Timsort (stable) at all times.

Knowing the default for your language is the prerequisite for trusting the standard library on multi-key sorts. Switching from a Python codebase to a Go one without flagging the stability change is how silent multi-key bugs ship.

Cost#

The Theta(n) auxiliary space on naive recursive Lomuto is the call stack on adversarial input; Sedgewick's tail-call fix bounds it at O(log n). Introsort's heap-sort fallback bounds the time at Theta(n log n), guaranteeing the worst-case bound without sacrificing average-case performance. The expected-time bound for RANDOMIZED-QUICKSORT comes from indicator-variable analysis: the expected number of comparisons is 2(n+1) H_n - 4n ≈ 2n ln n ≈ 1.39 n log_2 n, derived in CLRS §7.4.2.^[4:3] Three-way (Bentley-McIlroy fat partition) drops to Theta(n H) where H is the Shannon entropy of the key distribution, bounded above by log_2 k for k distinct keys; this is provably entropy-optimal among comparison sorts.^[5:1]

Pitfalls#

Problem ladder#

CORE spans Easy, Medium, Medium because the canonical Hard partition+quicksort problems on LeetCode are owned by adjacent chapters: LC 215 by Quickselect, LC 75 by Two pointers, opposite-direction. The chapter ships the cleanest partition exercises that demonstrate the pattern without poaching from neighbouring chapters.

CORE (solve all to claim chapter mastery)#

• LC 905 — Sort Array By Parity [Easy] • partition
• LC 2161 — Partition Array According to Given Pivot [Medium] • partition ★
• LC 324 — Wiggle Sort II [Medium] • quickselect-and-partition

STRETCH (optional)#

• LC 462 — Minimum Moves to Equal Array Elements II [Medium] • quickselect-via-partition
• LC 922 — Sort Array By Parity II [Easy] • partition

Where this leads#

The next chapter, Heap sort and the n log n lower bound, proves why no comparison-based algorithm can do better than Theta(n log n) in the worst case, and shows the third O(n log n) sort that achieves it in O(1) auxiliary space; the same heap sort that introsort uses as a fallback. After that, Linear-time sorts: counting, radix, bucket shows the algorithms that escape the lower bound by leaving the comparison model entirely. The partition primitive ratified here returns in Quickselect, where a single partition followed by recursion on one side gives expected O(n) selection. And the three-way partition variant becomes the substrate for Two pointers, opposite-direction, where Dijkstra's Dutch national flag specializes it to the K=3 case at the LC 75 level.

References#