Quicksort

What you're seeing

Each bar is a number; taller is larger. Quicksort works on a window of the array (the bright bars; dimmed bars are dormant sub-problems waiting their turn). It takes the rightmost element as the pivot (orange), then sweeps a scanner (blue) across the window, pushing every value ≤ the pivot into a growing region on the left (purple). When the sweep ends, the pivot swaps into the boundary — and turns green, because it is now exactly where it belongs in the final order and never moves again. Then the two sides recurse.

The rule

quicksort(a, lo, hi):
    if lo >= hi: return
    p = partition(a, lo, hi)        # pivot lands at p, in final place
    quicksort(a, lo, p-1)
    quicksort(a, p+1, hi)

partition(a, lo, hi):              # Lomuto, pivot = a[hi]
    i = lo
    for j = lo .. hi-1:
        if a[j] <= a[hi]:
            swap(a[i], a[j]); i++   # grow the ≤-pivot region
    swap(a[i], a[hi])              # drop pivot into the gap
    return i

The invariant

The partition keeps a running invariant as j sweeps: everything in a[lo..i) is ≤ the pivot, and everything in a[i..j) is > the pivot. So when the scan finishes, swapping the pivot into index i places it with all smaller values to its left and all larger to its right — meaning the pivot is now in its final sorted position (that's why it locks green). Correctness of the whole sort follows by induction: each recursive call sorts a strictly smaller sub-array, and the pivots between them are already final, so the pieces compose into a fully sorted array. Unlike merge sort, the divide step does all the work and the "combine" is free.

The cost

When a pivot lands near the middle, each partition roughly halves the problem → Θ(n log n), with small constants and great cache behavior (it sorts in place, scanning memory linearly). But the pivot choice is everything. With the simple last-element pivot shown here, an already-sorted or reversed input is the disaster case: every partition peels off just one element, giving n + (n−1) + … = Θ(n²) comparisons and Θ(n) recursion depth. Switch Initial order to Already sorted and watch the comparison counter balloon — the classic quicksort trap. Quicksort is not stable.

In the wild

Quicksort is the default in-memory sort almost everywhere — but never quite in the textbook form you see here. Real implementations are introsort (Musser, 1997): start with quicksort, but if the recursion depth exceeds ~2 log n (a sign of bad pivots heading toward the O(n²) cliff), switch to heapsort to guarantee Θ(n log n); and once a partition is small (≈16 elements) finish with insertion sort. They also pick the pivot defensively — median-of-three, or Pattern-Defeating Quicksort's adaptive scheme. C++'s std::sort mandates introsort-like worst-case behavior; the Rust and Go ecosystems use pdqsort variants. So the lesson here is double: quicksort's brilliance and its fragility, which is precisely why production wraps it in safeguards.

References

1. Hoare, C. A. R. "Quicksort." The Computer Journal 5(1):10–16, 1962. The original algorithm.
2. Cormen, Leiserson, Rivest & Stein. Introduction to Algorithms, 4th ed. (CLRS), §7 — Lomuto partition, the partition loop invariant, average vs worst case. MIT Press, 2022.
3. Musser, D. R. "Introspective Sorting and Selection Algorithms." Software: Practice and Experience 27(8):983–993, 1997 — introsort.
4. Sedgewick & Wayne. Algorithms, 4th ed., §2.3 (Quicksort) — partitioning, pivot strategy, not stable. algs4.cs.princeton.edu/23quicksort.