Quicksort

The problem

Sorting sits under a lot of everyday code: ordering query results, preparing data for binary search, grouping duplicates, finding a median. The simple quadratic sorts are fine for a few dozen items but fall over as n grows, and merge sort, which guarantees O(n log n), needs a second buffer as large as the input. Quicksort is the classic way to sort an array quickly in place: on typical data it is the fastest general-purpose comparison sort, and besides the array it needs only a short recursion stack.

Tony Hoare came up with it around 1959–60, as a visiting student at Moscow State University working on machine translation, where he needed to sort words so he could look them up efficiently in a dictionary. He published it in Communications of the ACM in 1961 as the ALGOL procedures Partition, Quicksort and Find (Algorithms 63 to 65), and described and analysed it in the 1962 paper Quicksort in The Computer Journal.

How it works

Quicksort is divide and conquer with the work done up front:

1. Pick a pivot. The diagram takes the last value of the range, the simplest rule.
2. Partition the range so that the values ≤ the pivot come first and the larger values after them, then swap the pivot in between. The pivot is now in its final position and never moves again.
3. Recurse on the part to its left and the part to its right. A part with zero or one value is already sorted.

Merge sort is the mirror image: it splits without looking at the values and does its work afterwards, merging sorted halves. Quicksort does its work before it recurses, so when the last call returns there is nothing left to combine.

Lomuto partitioning, the scheme in the diagram, keeps a boundary i and scans with j. Whenever a[j] ≤ pivot it swaps a[j] into slot i and moves i one step right, so a[lo:i] always holds the small values seen so far. It is named after Nico Lomuto, and Jon Bentley's Programming Pearls and the Introduction to Algorithms textbook made it the classroom standard because it is short and easy to prove correct. Hoare's original scheme moves two indices toward each other from both ends and swaps each pair that sits on the wrong side. It makes far fewer swaps (roughly a third as many as Lomuto's on random input, in a quick test) but its boundary conditions are subtler, and the pivot does not necessarily end at the split point. Neither scheme is stable.

The shape of the recursion sets the cost. Each level of the recursion compares the values in it with their pivots, so a level costs at most n comparisons. When pivots split their ranges evenly there are about log₂ n levels and the sort takes O(n log n): the 8 shuffled values in the diagram need 4 levels and 15 comparisons. When every pivot is the smallest or largest value in its range, each partition peels off only the pivot: n − 1 levels and n(n − 1)/2 comparisons, 28 for 8 values. Taking the last value as the pivot does exactly that to sorted and reverse-sorted input, which real programs produce all the time.

Choosing the pivot:

• First or last value: free, but quadratic on sorted or reversed input.
• A random value: the expected cost is O(n log n) on every input; a quadratic run is possible but very unlikely.
• Median of three (the first, middle and last values): sorted and reversed input split perfectly, for two or three extra comparisons per partition.
• Tukey's ninther: the median of three medians of three, nine samples in all, for large ranges. Bentley and McIlroy's Engineering a Sort Function (1993) uses it above 40 elements, and Go's pdqsort from 50.

No fixed rule stops a determined attacker. McIlroy's A Killer Adversary for Quicksort (1999) chooses the input's values lazily, while the sort runs, so that almost any quicksort, randomized ones included, goes quadratic; against a deterministic sort, the input it builds can be saved and replayed. That is why library sorts also cap the worst case with a guaranteed fallback (see the hybrids below).

Many equal keys. Because the test is ≤, Lomuto partitioning sends every copy of the pivot value to the left, so an array of identical values is quadratic even with a random pivot. Three-way partitioning splits the range into less than, equal to and greater than the pivot, and never looks at the equal block again; it is Dijkstra's Dutch national flag problem. With it, duplicates make quicksort faster instead of slower, and Bentley and McIlroy's paper gives a fast way to do it.

Bounding the stack. Recurse into the smaller part and loop on the larger one. Each recursive call then gets at most half of its parent's range, so no more than about log₂ n frames are ever on the stack, even when the running time is quadratic. A naive version needs a frame per level: sorting 2,000 already sorted values that way in Python exceeds the default recursion limit of 1,000.

Hybrids are what libraries actually ship:

• Introsort (David Musser, 1997) runs quicksort but switches to heapsort once the recursion passes a depth limit proportional to log n, so its worst case is O(n log n).
• Dual-pivot quicksort (Vladimir Yaroslavskiy, with Jon Bentley and Joshua Bloch) partitions around two pivots into three parts.
• pdqsort, Orson Peters' pattern-defeating quicksort, adds a heapsort fallback, scatters a few values when a partition comes out badly unbalanced, tries a short insertion sort on ranges that look sorted already, and sorts input with k distinct values in O(nk).

Quickselect. Partition once, then continue only into the side that holds index k: the k-th smallest value (a median, a percentile) comes out in O(n) time on average and O(n²) at worst, without sorting the rest. Hoare published it as Find alongside quicksort; C++ offers it as std::nth_element, typically implemented as introselect.

Code

import random


def quicksort(a, lo=0, hi=None):
    """Sort the list a in place: Lomuto partition, random pivot."""
    if hi is None:
        hi = len(a) - 1
    while lo < hi:
        p = partition(a, lo, hi)
        # Recurse into the smaller side and loop on the larger one,
        # so the call stack stays O(log n) deep.
        if p - lo < hi - p:
            quicksort(a, lo, p - 1)
            lo = p + 1
        else:
            quicksort(a, p + 1, hi)
            hi = p - 1


def partition(a, lo, hi):
    r = random.randint(lo, hi)        # random pivot, parked at the end
    a[r], a[hi] = a[hi], a[r]
    pivot = a[hi]
    i = lo                            # a[lo:i] holds values <= pivot
    for j in range(lo, hi):
        if a[j] <= pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]         # the pivot lands in its final place
    return i


data = [6, 3, 8, 1, 9, 2, 7, 5]
quicksort(data)
print(data)  # [1, 2, 3, 5, 6, 7, 8, 9]

The while loop sorts the larger side itself, which keeps the stack O(log n) deep, and the random pivot makes sorted input harmless. The code is tested against sorted() on random, sorted, reversed, all-equal, empty and one-item lists. All-equal input still takes O(n²) time with this two-way partition; three-way partitioning fixes that.

Complexity

When to use it

• Sorting arrays in memory when equal keys need not keep their input order: numbers, strings, records with a unique key. The unstable sorts in standard libraries are built on it.
• When memory is tight: it needs no buffer the size of the input, unlike merge sort.
• Selecting without sorting: a median, the top k, a percentile (quickselect).
• Not when the order of equal keys matters, as when sorting by one key and then by another: use a stable sort such as Timsort or merge sort.
• Not when you need a guaranteed worst case and cannot add a fallback: heapsort and merge sort are O(n log n) on every input.
• Not for linked lists: merge sort sorts a list by relinking nodes, stably and in guaranteed O(n log n), while quicksort's strengths (swaps in place, cache-friendly scans) need an array.

Trade-offs

• Fast on average, quadratic at worst. Plain quicksort goes O(n²) on sorted input with a naive pivot, on many equal keys with two-way partitioning, and on purpose under an adversary. Random or sampled pivots, three-way partitioning and a depth limit (introsort) keep the speed without the risk.
• In place, but not stable. The long-distance swaps that make it cheap in memory are the same ones that scramble equal keys.
• Cache-friendly. Partitioning streams through contiguous memory. Heapsort, also in place, jumps between distant parents and children, which is one reason it serves as the fallback rather than the main act.
• Recursion overhead on small ranges. Calls cost more than they save on a handful of values, so implementations hand ranges below a cutoff to insertion sort (16 elements in libstdc++).

Implementation notes

• C++: the standard requires std::sort to make O(n log n) comparisons in the worst case (C++98 asked for it only on average, until defect report LWG 713), which plain quicksort cannot promise. libstdc++ uses introsort: a median-of-three pivot, heapsort once the recursion reaches a depth limit of 2 log₂ n, and insertion sort for short ranges; libc++ has met the requirement since LLVM 14. std::nth_element is O(n) on average.
• Java: Arrays.sort on primitive arrays has been a dual-pivot quicksort since Java 7, and the current OpenJDK code also switches to heapsort when the recursion gets too deep. Arrays of objects use TimSort instead: equal primitives are indistinguishable, but equal objects are not, so only object sorts need to be stable.
• Go: sort.Sort has used pattern-defeating quicksort since Go 1.19, and so does slices.Sort, which sort.Ints and its siblings call since Go 1.22. Neither is stable; sort.Stable and slices.SortStableFunc are.
• Rust: sort_unstable is based on ipnsort (Lukas Bergdoll and Orson Peters), a quicksort with a heapsort fallback that runs in linear time on sorted and reversed input; the stable sort is driftsort, a hybrid of quicksort and merge sort.
• Python: list.sort() and sorted() use Timsort, which is stable and takes advantage of runs that are already in order.
• Databases: PostgreSQL sorts in memory with Bentley and McIlroy's quicksort (sort_template.h), changed to check for presorted input and to recurse into the smaller partition, a change its source comments justify with stack overflows seen in production. EXPLAIN ANALYZE reports such a sort as Sort Method: quicksort; input too large for work_mem is sorted in runs that are merged from temporary files.
• Percentiles: an exact p99 over a batch of latency samples is a selection problem, which quickselect answers in O(n) on average without sorting the batch. Monitoring systems more often keep histograms or sketches that answer approximately in bounded memory; see SLOs & Error Budgets.