Quicksort — Divide-and-Conquer Sorting With Pivot

The partition invariant — everything else is bookkeeping

Quicksort has exactly one non-trivial operation. Partition takes a range and an element called the pivot, and rearranges the range so that every key on one side compares no greater than the pivot and every key on the other side compares no less. It returns a split point. The recursion that follows is trivial: sort the left part, sort the right part, and do nothing to combine them, because the partition already guaranteed that everything left is ordered relative to everything right.

That absence of a combine step is the structural difference from mergesort, where the recursion is trivial and all the work happens on the way back up. Quicksort does its work on the way down. The consequence is that quicksort needs no auxiliary array — every rearrangement is a swap inside the original buffer — while a straightforward merge needs n extra slots.

Two properties of the split point are load-bearing and are the source of most quicksort bugs. First, the split must be strict: each recursive call must receive a range strictly smaller than the one it was given, or the algorithm loops forever. Second, whether the element at the split point is itself already in final position depends on the partition scheme, and getting that wrong produces a sort that is subtly incorrect rather than obviously broken.

Lomuto partition — the one you can prove on a whiteboard

Lomuto's scheme keeps a single moving boundary. It takes the last element as the pivot, sweeps a cursor j across the range once, and maintains the invariant that everything in a[lo..i] is <= pivot and everything in a[i+1..j-1] is > pivot. When the sweep ends, one final swap drops the pivot immediately after the small region.

def lomuto_partition(a, lo, hi):
    pivot = a[hi]                 # pivot is the last element
    i = lo - 1                    # end of the "known <= pivot" prefix
    for j in range(lo, hi):
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]   # drop the pivot into its final slot
    return i + 1

def quicksort_lomuto(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo < hi:
        p = lomuto_partition(a, lo, hi)
        quicksort_lomuto(a, lo, p - 1)      # p is excluded: it is placed
        quicksort_lomuto(a, p + 1, hi)

The invariant is easy to state and easy to check, which is why this is the version in most course notes. It also has a property the other scheme lacks: the returned index p holds the pivot in its final sorted position, so the recursive calls exclude it. That makes Lomuto the natural base for quickselect, where you need to know exactly which rank you just placed — see selection algorithms.

The cost is movement. An instrumented run on 100,000 random 32-bit keys measured Lomuto at about 9.9 swaps per element against 3.8 for Hoare — roughly two and a half times the data movement for the same sort. Lomuto swaps on every element that compares small, even when that element is already sitting where it belongs; Hoare swaps only pairs that are genuinely on the wrong sides.

Hoare partition — fewer swaps and three off-by-one traps

Hoare's original 1961 scheme runs two cursors toward each other. The left cursor advances while it sees keys below the pivot, the right cursor retreats while it sees keys above it, and when both stall the two offending elements are swapped. It stops when the cursors cross.

def hoare_partition(a, lo, hi):
    pivot = a[(lo + hi) // 2]     # a VALUE, not an index -- it will move
    i, j = lo - 1, hi + 1
    while True:
        i += 1
        while a[i] < pivot:       # no bounds check needed: pivot stops it
            i += 1
        j -= 1
        while a[j] > pivot:
            j -= 1
        if i >= j:
            return j              # NOT j + 1, and NOT i
        a[i], a[j] = a[j], a[i]

def quicksort_hoare(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo < hi:
        p = hoare_partition(a, lo, hi)
        quicksort_hoare(a, lo, p)           # p is INCLUDED on the left
        quicksort_hoare(a, p + 1, hi)

Three details are traps. The pivot is copied by value. Taking a[(lo+hi)//2] as an index and dereferencing it later fails, because the swaps move that element. The cursor increments happen before the inner loops, not after — this is a do-while in disguise, and it is what guarantees each cursor moves at least one step per outer iteration, which is what makes the returned range strictly smaller. The return value is j, and the left recursion includes it. Returning i, or excluding j the way Lomuto excludes its pivot, gives a routine that sorts most inputs and quietly drops elements on others.

Hoare does slightly more comparisons than Lomuto — the same instrumented run measured about 2.44 million versus 2.01 million at n = 100,000 — because the two scans each re-test the element they stop on. On any type where a swap is more expensive than a comparison, which is most types larger than a machine word, that trade is strongly worth taking.

Balanced splits, unbalanced splits, and why depth is the only thing that matters

Partition is linear, so the running time obeys T(n) = T(k) + T(n - k - 1) + Θ(n), where k is the size of the left part. Every level of the recursion tree does Θ(n) total work — the ranges at a level are disjoint and cover the array — so the total is Θ(n) times the depth. Nothing else about the split shape matters. The general machinery for solving recurrences like this lives in Big-O notation.

An even split gives k = n/2 and depth lg n, hence Θ(n log n). A maximally lopsided split gives k = 0 every time, depth n, and Θ(n²). The interesting question is how much imbalance the algorithm actually tolerates, and the answer is startling: a constant-fraction split is enough. Suppose every partition splits 99:1. The deepest branch shrinks by a factor of 0.99 each level, so it reaches size 1 after log(n) / log(100/99) levels — about 69 lg n. That is a constant factor worse than a perfect split, not an asymptotic change.

So quicksort does not need good pivots. It needs pivots that are not systematically terrible. A pivot landing anywhere in the middle 98% of the sorted order still yields O(n log n). The failure mode is not an occasional bad pivot; it is a rule that picks a bad pivot at every level on the same input. The formal statement — that a uniformly random pivot gives expected Θ(n log n) regardless of input — belongs to randomized quicksort, where the expectation argument is done properly.

The quadratic inputs you actually hit

Textbook worst cases sound theoretical. These three are not; each one has taken down production systems.

Already-sorted data with a first- or last-element pivot. Lomuto as written above takes a[hi]. On sorted input that is the maximum, so every partition yields n-1 on the left and nothing on the right. This is the most common accidental worst case in the wild, because data arrives sorted far more often than chance would suggest: it came out of a database with an ORDER BY, or off a log with monotonic timestamps, or from a previous sort someone forgot about.

All-equal keys. Run the Lomuto partition on nine identical elements and it returns index 8 — the test is <=, so every element compares small, and the pivot ends at the far end. Depth n again. This one is worse than the sorted case because it is invisible: sorting a million records by a status field with four distinct values looks like an ordinary workload. Hoare partition on the same nine identical elements returns index 4 — a perfect split — because its cursors both stop immediately on equal keys and swap past each other. That asymmetry is the single strongest practical argument for Hoare.

Adversarial input against a deterministic rule. Any fixed pivot rule can be defeated by an input constructed against it. McIlroy's 1999 anti-quicksort demonstrates this concretely: a comparison function that answers consistently but decides values lazily can drive a median-of-three qsort into Θ(n²). If untrusted input reaches your sort, a deterministic pivot rule is a denial-of-service vector, not merely a performance risk.

Pivot selection — median-of-three, the ninther, and what they buy

Given that only systematic badness hurts, pivot rules are cheap insurance rather than optimisation. In rough order of cost:

Middle element. One index computation. Fixes the sorted-input case completely and costs nothing, which is why it appears in the Hoare code above. It is still deterministic and still defeatable.

Median-of-three. Sort the first, middle and last elements in place and use the middle one. Three comparisons, at most three swaps, and as a side effect it plants sentinels at both ends of the range so the inner scan loops need no bounds check.

def median_of_three(a, lo, hi):
    mid = lo + (hi - lo) // 2     # not (lo + hi) // 2 -- avoids overflow in C
    if a[mid] < a[lo]:
        a[lo], a[mid] = a[mid], a[lo]
    if a[hi] < a[lo]:
        a[lo], a[hi] = a[hi], a[lo]
    if a[hi] < a[mid]:
        a[mid], a[hi] = a[hi], a[mid]
    return mid                    # postcondition: a[lo] <= a[mid] <= a[hi]

Median-of-three cannot produce the absolute extreme of the range, which alone rules out the degenerate split. It also makes already-sorted input a best case rather than a worst case. On random data it is a modest constant-factor win as well: an instrumented Hoare sort of 200,000 random keys used about 1.34 n lg n comparisons with median-of-three against 1.46 with a plain middle pivot and 1.57 with a first-element pivot — roughly 8% off the middle-pivot count. Note the lo + (hi - lo) // 2 midpoint: in a language with fixed-width integers, (lo + hi) / 2 overflows on large arrays, the bug that sat in the JDK's binary search for nine years.

The ninther (Tukey's median of medians of three) samples nine elements as three groups of three, takes each group's median, then the median of those. It is the standard escalation for large ranges — libraries typically switch to it above a few hundred elements — because the sample quality matters more when the subarray is big enough for a bad split to cost real time. A random pivot moves the guarantee from the input to the coin flips, which is the only way to defeat an adversary; see randomized quicksort.

Repeated keys and the three-way partition

Two-way partitioning treats keys equal to the pivot as ordinary elements, so a range of one million records with four distinct keys still gets recursed on until the ranges are singletons. That is Θ(n log n) work to discover something the first partition already knew. The fix is to make partition produce three regions instead of two: less, equal, greater. The equal band is finished — it never gets recursed on.

def quicksort3(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo >= hi:
        return
    pivot = a[lo + (hi - lo) // 2]
    lt, i, gt = lo, lo, hi        # [lo,lt) < pivot, [lt,i) == pivot,
    while i <= gt:                # (gt,hi] > pivot, [i,gt] unexamined
        if a[i] < pivot:
            a[lt], a[i] = a[i], a[lt]
            lt += 1
            i += 1
        elif a[i] > pivot:
            a[gt], a[i] = a[i], a[gt]
            gt -= 1               # i does NOT advance: a[i] is unexamined
        else:
            i += 1
    quicksort3(a, lo, lt - 1)
    quicksort3(a, gt + 1, hi)     # the whole equal band is skipped

This is Dijkstra's Dutch national flag partition, and the invariant is the whole algorithm: [lo, lt) holds keys below the pivot, [lt, i) holds keys equal to it, (gt, hi] holds keys above it, and [i, gt] is the shrinking unexamined middle. The asymmetry in the loop is the part people get wrong: when an element is swapped down from the gt end, i must not advance, because the element that just arrived at position i has never been examined. When an element is swapped up from the lt end, i does advance, because the element arriving from lt is already known to be equal to the pivot.

On a key with d distinct values the three-way sort runs in O(n log d), which for four distinct values in a million records means two passes instead of twenty. The cost is a slightly heavier inner loop — two comparisons per element instead of one on the common path — so it is not a free win on all-distinct data. Libraries handle this by detecting duplicates rather than always paying: a partition that returns a suspiciously lopsided split with many equal keys triggers the three-way path.

Bounding the stack — recurse small, loop large

Quicksort is advertised as an in-place sort with O(1) auxiliary space. That is false as usually written, because the recursion stack is space. A degenerate split gives n stack frames, and on a 32 MB array of 4-byte keys that is eight million frames — a segfault, not a slow sort. Even on random data the depth is worse than lg n: the instrumented run at n = 100,000 reached depth 40 against lg n ≈ 16.6.

The fix costs one comparison per partition. After splitting, recurse into the smaller side and handle the larger side by mutating the loop variables — the recursive call on the larger side was a tail call anyway, so eliminating it by hand loses nothing.

def quicksort_bounded(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    while lo < hi:
        p = hoare_partition(a, lo, hi)
        if p - lo < hi - p:              # left side is the smaller one
            quicksort_bounded(a, lo, p)  # recurse into the small side
            lo = p + 1                   # and loop on the large side
        else:
            quicksort_bounded(a, p + 1, hi)
            hi = p

Because the recursive call always receives at most half the current range, the stack depth is bounded by lg n unconditionally — 64 frames covers any array that fits in a 64-bit address space, whatever the pivots do. The same instrumented run that hit depth 40 with the plain version hit depth 11 with this one. Note that this is a bound on space, not time: a pathological input still runs in Θ(n²), it just no longer crashes first. Relying on the compiler to do this for you is unwise; tail-call elimination is not guaranteed in C or C++ and does not exist in Java or Python at all.

What production sorts actually ship — introsort, pdqsort, dual-pivot

No serious library ships bare quicksort. What they ship is a hybrid with three layers of defence, and the pattern is worth knowing because it explains the performance cliffs you will and will not observe.

Introsort (Musser, 1997) is the C++ std::sort strategy. It runs quicksort with a depth budget of about 2 lg n. If a branch exhausts the budget — which only happens if the pivots have been consistently awful — that branch switches to heapsort, which is Θ(n log n) in the worst case. Below a cutoff of roughly 16 elements it stops partitioning entirely and leaves the range nearly sorted for a single final insertion-sort pass over the whole array. The result is quicksort's constants with heapsort's guarantee.

import heapq

CUTOFF = 16

def insertion_sort(a, lo, hi):
    for i in range(lo + 1, hi + 1):
        v = a[i]
        j = i - 1
        while j >= lo and a[j] > v:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = v

def heapsort_range(a, lo, hi):
    h = a[lo:hi + 1]              # a real in-place sift is better; see the
    heapq.heapify(h)              # heap article. This is the same algorithm.
    for k in range(lo, hi + 1):
        a[k] = heapq.heappop(h)

def introsort(a):
    n = len(a)
    if n < 2:
        return
    _intro(a, 0, n - 1, 2 * n.bit_length())   # depth budget ~ 2 lg n
    insertion_sort(a, 0, n - 1)               # one final near-sorted pass

def _intro(a, lo, hi, depth):
    while hi - lo > CUTOFF:
        if depth == 0:
            heapsort_range(a, lo, hi)         # bail out, guarantee n lg n
            return
        depth -= 1
        p = hoare_partition(a, lo, hi)
        if p - lo < hi - p:
            _intro(a, lo, p, depth)
            lo = p + 1
        else:
            _intro(a, p + 1, hi, depth)
            hi = p

The heap step above delegates to a library heap for brevity; a real implementation sifts in place over the subrange, which is the version described in heap operations. pdqsort (pattern-defeating quicksort) is the modern refinement, used by Rust's sort_unstable. It adds branchless block partitioning, detects already-sorted runs, and reacts to a bad split by shuffling a few elements rather than waiting for the depth budget to expire. Dual-pivot quicksort (Yaroslavskiy) partitions into three regions using two pivots at once and is what Java's Arrays.sort uses on primitive arrays; Java's object overload uses a stable merge sort instead, for the reason in the next section.

Branch misprediction and the cache — why quicksort wins in wall clock

Quicksort, mergesort and heapsort are all Θ(n log n), and quicksort is reliably the fastest of the three on random data in a flat memory model that does not exist. The real reasons are architectural.

Locality. Partition is two sequential scans over one contiguous range. The hardware prefetcher handles it perfectly, and once a subarray fits in L2 the entire remaining recursion for that subarray touches no memory outside it. Heapsort, by contrast, jumps between index i and 2i+1, which for a large array is a cache miss per level — that is why it loses in practice despite a better worst case.

No auxiliary buffer. Mergesort's n extra slots halve the effective cache and add allocation to the critical path. On a machine where the array does not comfortably fit in memory alongside its copy, that is not a constant factor.

Branch prediction is the modern villain. The comparison inside partition is unpredictable by construction — on random data it goes each way about half the time — so a naive partition mispredicts roughly once per element, at 15 to 20 cycles each. That is why pdqsort's block partitioning exists: it computes the comparison results into a small offset buffer with no branch at all, then performs the swaps from that buffer. The comparison count is unchanged and the wall-clock time drops substantially. If you profile a sort and the instruction count looks fine while the time does not, look at the mispredict counter before you look at the algorithm.

Stability, and when to reach for something else

Quicksort is not stable. Partition swaps elements across arbitrary distances, so two records with equal keys can emerge in either order, and no cheap patch fixes this — the usual workaround is to make the key unique by appending the original index, which costs O(n) space and defeats the point. When stability matters, and it usually does for user-visible multi-column sorting, use a stable merge sort. This is exactly why Java sorts primitives with dual-pivot quicksort and objects with TimSort: primitives have no identity, so stability is unobservable.

Reach for something else when the data does not fit in memory — external sorting is merge-based because merging streams sequentially and partitioning does not. Reach for something else when you need a hard worst-case bound with no fallback machinery, such as in a real-time path. Reach for counting or radix sort when keys are small integers, where the n log n comparison lower bound does not apply because you are not comparing. And if you only need the k smallest elements or the median, do not sort at all: quickselect recurses into one side of the partition instead of both, giving expected linear time — see selection algorithms.

Everywhere else, the checklist is short. Use a middle or median-of-three pivot so sorted input is a best case. Use Hoare or three-way partitioning so equal keys do not degenerate. Recurse on the smaller side so the stack is bounded. Cut over to insertion sort on small ranges. Add a depth limit with a heapsort fallback if adversarial input is possible. Those five lines of defence are the difference between the routine in the textbook and the one in your standard library.