Quicksort

What this chapter covers

Quicksort is merge sort's great rival: also divide-and-conquer, also O(n log n) on average, but it splits the problem the opposite way. Instead of dividing blindly in half and merging sorted results, it picks a pivot and partitions — rearranging so everything smaller sits left of the pivot and everything larger sits right — then recurses into each side. The pivot lands in its final place and no merge is needed, so all the work happens in place, on the way down. That makes quicksort usually the fastest comparison sort in practice. It also makes it dangerous: a bad pivot turns O(n log n) into O(n²), and this chapter shows exactly that happening.

A bit of history

Quicksort has one of the best origin stories in computing. Tony Hoare invented it in 1959 as a 25-year-old exchange student in Moscow, working on a machine-translation project. He needed to sort the words of a sentence to look them up in a dictionary, realized that partitioning around a pivot would do it, and couldn't at first prove to his colleagues that the recursive idea would work. He published it in 1961, and it's been the default sort for arrays ever since — it's C's qsort, the basis of C++ and Rust's unstable sorts, and the reason "quicksort" is the sort most programmers name first. Hoare later won the Turing Award, and quicksort is the achievement his name is most tied to. Its enduring lesson is also a cautionary one: the algorithm is elegant and fast, and it has a worst case that has bitten real systems, which is why the pivot strategy is a chapter in itself.

The intuition

The key operation is the partition. Pick one element as the pivot. Now sweep through the rest and shuffle them so that everything less than the pivot ends up on its left and everything greater on its right. When you're done, the pivot is in its final sorted position — nothing will ever move it again — and you have two smaller unsorted regions, one on each side. Sort those two regions the same way, and the whole array is sorted. No merge step, because the partition already put everything on the correct side of the pivot.

That's the elegance: the array gets sorted in place, with the pivots snapping into their final spots one by one. But notice what the whole thing rests on — the pivot splitting the array into two balanced pieces. If the pivot is the median, each side is half the size and you get log n levels, just like merge sort. If the pivot is always the smallest or largest element, one side is empty and the other is everything but the pivot, so you get n levels of O(n) work — a quadratic. The pivot is the whole ballgame.

Complexity: how it scales

On average — over random pivots or random input — quicksort's partitions are balanced enough that it runs in $O(n \log n)$, with a small constant that often beats merge sort because it's in place and cache-friendly. Its space is just the recursion stack, $O(\log n)$, since it sorts within the array itself. But the worst case is $O(n^2)$: if every pivot is the smallest or largest remaining element, each partition removes only the pivot, so you do n partitions of O(n) work. With the last-element pivot this implementation uses, the worst case is already-sorted input — the most common real-world input there is. The chart below sorts random data, where quicksort tracks the library sort:

But feed the same algorithm sorted input and it falls off a cliff. On 4000 elements, our quicksort took about 2 ms on random data and 311 ms on already-sorted data — 141 times slower for the same size, purely because the pivot was pessimal every time:

What it's good at, what it isn't

Quicksort is the fastest general-purpose comparison sort in practice, and the reason is constants, not asymptotics. It sorts in place, so it doesn't pay merge sort's O(n) memory tax; it partitions with simple swaps that the CPU cache loves; and its inner loop is tight. When you're sorting an array of numbers and don't need stability or worst-case guarantees, quicksort (well-pivoted) is the one to beat.

Its weaknesses are the flip side. The O(n²) worst case is real and, with a naive pivot, is triggered by ordinary sorted or reverse-sorted input — a genuine denial-of-service risk if an attacker controls the data. It's not stable, so equal elements can be reordered. And it needs random access, so it's wrong for linked lists (where merge sort shines). The worst case is manageable — randomize the pivot or fall back to heapsort — but it's a real thing you have to actively defend against, unlike merge sort's guarantee.

The data, or the inputs

The face-off sorts random integers against the library sort. A second chart feeds the same quicksort random versus already-sorted input, to expose the O(n²) worst case directly. And the animation partitions ten elements, recording every comparison and swap so you can watch the pivot sweep the array and snap into place.

Build it, one function at a time

The recursion partitions, then sorts each side — recursing into the smaller side and looping on the larger to keep the stack shallow even when a pivot is bad:

def quicksort(a, probe=None):
    """O(n log n) average, O(n^2) worst: partition around a pivot, recurse on each
    side. In place — the rearranging happens in the array itself, no merge."""
    a = list(a)
    _qsort(a, 0, len(a) - 1, probe)
    return a


def _qsort(a, lo, hi, probe):
    # Recurse into the SMALLER partition and loop on the larger. This bounds the
    # recursion depth to O(log n) even when the partitions are unbalanced, so a
    # bad pivot costs time but never a stack overflow.
    while lo < hi:
        p = _partition(a, lo, hi, probe)
        if p - lo < hi - p:
            _qsort(a, lo, p - 1, probe)
            lo = p + 1
        else:
            _qsort(a, p + 1, hi, probe)
            hi = p - 1

The partition is the heart of it. Take the last element as the pivot, sweep with a boundary i that marks the end of the "less than pivot" region, swap each smaller element up to the boundary, then drop the pivot into the boundary — its final spot:

def _partition(a, lo, hi, probe=None):
    """Lomuto partition. Take the last element as the pivot and sweep from lo to hi,
    keeping a boundary i such that everything left of it is smaller than the pivot.
    Each element smaller than the pivot is swapped up to the boundary; finally the
    pivot is swapped into the boundary, landing in its permanent sorted position."""
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if probe is not None:
            probe.append({"arr": list(a), "pivot": hi, "i": i, "j": j, "lo": lo, "hi": hi, "placed": False})
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]       # drop the pivot into its final place
    if probe is not None:
        probe.append({"arr": list(a), "pivot": i, "i": i, "j": i, "lo": lo, "hi": hi, "placed": True})
    return i

Watch it work

Here's quicksort partitioning ten bars. Purple is the pivot (the last element of the current region); yellow is the bar being compared to it; blue bars have been found smaller and swapped into the growing "less than pivot" zone on the left; gray bars are still unprocessed; dark bars are outside the current partition. Step through it: the yellow cursor sweeps left to right, blue collects the small ones, and when the sweep finishes the pivot swaps into place and turns green — locked in its final sorted position. Then the two regions on either side of it get partitioned the same way:

The complete code

Both versions in one place — flip between them. The from-scratch tab is our quicksort with Lomuto partitioning. The library tab is list.sort — Timsort in CPython's case, though C's qsort and C++/Rust's unstable sorts are introsort: quicksort that monitors its recursion depth and switches to heapsort if a bad pivot makes it too deep, getting quicksort's speed with merge sort's worst-case guarantee.

"""Quicksort — the other O(n log n) sort, and the one most standard libraries use
for arrays of primitives. Like merge sort it's divide-and-conquer, but it splits
differently: pick a pivot, partition the array so everything smaller is on its left
and everything larger on its right, then recurse into each side. The pivot lands in
its final sorted position, and no merge is needed — the work happens on the way down,
in place, which is why quicksort is usually faster than merge sort in practice.

The catch is the pivot. A good split gives O(n log n); a consistently bad one gives
O(n²). This implementation uses the last element as the pivot (simple, and it lets us
demonstrate the worst case), and recurses into the smaller side first to keep the
stack depth O(log n).
"""


# region: quicksort
def quicksort(a, probe=None):
    """O(n log n) average, O(n^2) worst: partition around a pivot, recurse on each
    side. In place — the rearranging happens in the array itself, no merge."""
    a = list(a)
    _qsort(a, 0, len(a) - 1, probe)
    return a


def _qsort(a, lo, hi, probe):
    # Recurse into the SMALLER partition and loop on the larger. This bounds the
    # recursion depth to O(log n) even when the partitions are unbalanced, so a
    # bad pivot costs time but never a stack overflow.
    while lo < hi:
        p = _partition(a, lo, hi, probe)
        if p - lo < hi - p:
            _qsort(a, lo, p - 1, probe)
            lo = p + 1
        else:
            _qsort(a, p + 1, hi, probe)
            hi = p - 1
# endregion


# region: partition
def _partition(a, lo, hi, probe=None):
    """Lomuto partition. Take the last element as the pivot and sweep from lo to hi,
    keeping a boundary i such that everything left of it is smaller than the pivot.
    Each element smaller than the pivot is swapped up to the boundary; finally the
    pivot is swapped into the boundary, landing in its permanent sorted position."""
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if probe is not None:
            probe.append({"arr": list(a), "pivot": hi, "i": i, "j": j, "lo": lo, "hi": hi, "placed": False})
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]       # drop the pivot into its final place
    if probe is not None:
        probe.append({"arr": list(a), "pivot": i, "i": i, "j": i, "lo": lo, "hi": hi, "placed": True})
    return i
# endregion

"""`list.sort` / `sorted` is Timsort (a merge sort), not quicksort — CPython chose a
stable merge sort. But quicksort is what many other languages use for arrays of
primitives: C's `qsort`, and C++/Rust's unstable sort, are introsort — quicksort with
a heapsort fallback to dodge the O(n²) worst case. So the honest counterpart is the
built-in in-place sort, and the point of the face-off is that our quicksort matches
its O(n log n) on random data and blows up on the input that makes quicksort quadratic.
"""


# region: sort_builtin
def sort_builtin(a):
    """In-place sort via list.sort (Timsort): O(n log n) worst case, stable, in C."""
    a = list(a)
    a.sort()
    return a
# endregion

Scratch vs library

On random data our quicksort sorted 80000 integers in about 61 ms against the library sort's 7.4 ms — roughly 8 times slower, the familiar Python-versus-C constant. Notice it beat our merge sort from last chapter (86 ms) on the same task, which is the practical point: quicksort's in-place partitioning has a smaller constant than merge sort's allocate-and-merge, so among O(n log n) sorts it's usually the fastest, and that's why it's the array-sorting default in most languages. But the worst-case chart is the lesson that outlasts the benchmark: the very same code that's fast on random data is 141 times slower on sorted data, because a fixed pivot met its adversary. The library never has this problem — Timsort has no bad case, and introsort caps quicksort's depth — which is the deeper reason to reach for the built-in.

Where you'll actually meet it

Quicksort, in its hardened introsort form, is the sort behind qsort in C, std::sort in C++, and the unstable sort in Rust and many other languages — anywhere you sort an array of primitives and don't need stability. Its partition step is independently useful: it's the core of quickselect (next chapter), which finds the k-th smallest element in O(n) without fully sorting, and partitioning shows up in three-way splits for data with many duplicates (the "Dutch national flag" problem). Even where the library uses merge sort, understanding quicksort is how you understand why sorting is O(n log n) and where its sharp edges are.

Takeaways

Quicksort partitions around a pivot — smaller left, larger right, pivot into place — and recurses, sorting in place in $O(n \log n)$ average time with a small constant that usually makes it the fastest comparison sort. Its cost is the pivot: a bad one gives $O(n^2)$, and with a naive fixed pivot the trigger is ordinary sorted input, so you must randomize the pivot or use a library sort that does. It's the counterweight to merge sort — faster and in-place, but with a worst case merge sort doesn't have.

One more sort completes the comparison trio. Heapsort, next, is the one that gets $O(n \log n)$ guaranteed, like merge sort, but in place, like quicksort — the best of both on paper — using a data structure we haven't built yet: the binary heap. It's also the fallback that introsort switches to when quicksort misbehaves, so it closes the loop on this chapter's worst case.