Why quicksort is fast in practice

You have read that quicksort is O(n²) in the worst case and O(n log n) on average, and that standard libraries use it anyway, and the two statements sit uneasily together until you notice they are not really in tension: the worst case is real, and real implementations are built specifically to avoid meeting it. What the complexity classes alone do not explain is why quicksort keeps winning where it does — and that has less to do with how cleverly the pivot is chosen than with how the algorithm touches memory while it works.

The algorithm underneath all of this is three steps, and it is worth having them in view before the argument starts. Pick one element of the array — the pivot. Rearrange the array so that everything smaller than the pivot ends up on one side of it and everything larger on the other; the pivot is now sitting exactly where it belongs in the finished order, and it never has to move again. Then do the same thing to each of the two sides, and to their sides, until the pieces are one element long. That rearranging step is the partition, and almost everything on this page is about it: which element gets picked as the pivot decides how evenly the array splits, and how the partition walks the array decides what the machine’s memory does while it works.

The worst case, and why you do not meet it#

Quicksort’s quadratic case comes from a pivot that splits the array as unevenly as possible on every recursive call. A rule that always picks a fixed position — the first element, say — is trivially defeated by an array already sorted in that direction: every partition puts one element on one side and everything else on the other, and the recursion never gets any shallower. The mirror case shows up on reverse-sorted input against a rule that always takes the last element. Neither input is exotic. A mostly-sorted log file or an already-ordered import produces exactly this shape routinely, which is exactly why no serious implementation ships a fixed-position pivot rule.

What ships instead is pivot selection built to resist that pattern. Go’s own standard library documents choosing the pivot as a median-of-three for shorter slices — comparing a small sample of candidates and taking the middle one rather than trusting any single position — and, separately, a step that deliberately scatters some elements before partitioning to break the kind of regular pattern a single fixed position cannot see coming. .NET’s own documentation for Array.Sort describes a different defence: its introsort counts the partitions the sort has produced against a budget fixed once by the size of the input array as a whole — not recomputed for whichever partition happens to be in hand — and once that budget is exceeded, it abandons quicksort’s recursion and finishes with heapsort instead — an algorithm whose worst case is already O(n log n), so the switch caps how bad quicksort’s bad luck is allowed to get. Below a certain partition size, the same implementation switches again, to a plain insertion sort, because a small partition is cheaper to finish directly than to keep splitting.

None of this is luck. “Quicksort is O(n²) in the worst case” is true of the bare algorithm with an adversarial, fixed pivot rule. A claim about what a specific sort function does on your input is a claim about that function’s pivot strategy and its fallback — a different, checkable thing, and one a library’s own documentation states directly rather than leaving to be assumed.

The reason that is not in the complexity#

Here is what the complexity classes do not capture. Quicksort partitions the array in place, walking it with pointers that scan toward each other and swap when they cross a violation of the pivot rule; every read and write stays inside the same contiguous block of memory, visited in close to the order that block sits in. Mergesort, run to the same O(n log n) average bound, does something different underneath: it allocates a second region to hold a merged run, copies elements into it, and writes the result back, over and over, one merge level at a time. Complexity notation counts comparisons per level and multiplies by the number of levels; it does not ask where those comparisons happen to point in memory, because that was never part of what the notation measures.

That omission matters because sequential access suits how memory hardware is built to be read: a machine that fetches from a contiguous block gets to reuse work it already did nearby, in a way that jumping between two separate regions does not. Quicksort’s in-place partition is exactly the sequential-access case; mergesort’s two-region copy is exactly the pattern that benefits less from it, even though the two algorithms make close to the same number of comparisons to get there. That effect has a name — cache locality — and it is the sense in which cache locality does more of the real work than the pivot rule does: the pivot rule is what keeps the comparison count near its average case, and it is what a comparison count was never going to show in the first place.

The site’s own sorting visualiser has no quicksort in it at all — only insertion sort and merge sort, stepped through comparison by comparison on the same array — and that gap is worth sitting with rather than working around. What the tool proves is real: two algorithms with different complexity classes can be made to pull apart or draw level depending on the order of the input, and a running comparison count is exactly the evidence for that. What it cannot prove is this section’s claim, because quicksort and mergesort are close enough on average comparison count that a tool built to count comparisons would call them a tie — the memory-access difference that actually separates them in practice never shows up on that axis.

This article assumes average case and worst case as already-separate ideas going in. Building the ideas an article like this one starts from, rather than assuming them, is the job the site’s foundations pillar takes on — one level back from where this piece begins, and the level a reader who wants them from nothing should be reading at.

Is your sort even quicksort?#

The recognisable failure starts from an assumption rather than a check: that a language’s sort() call is quicksort, and that quicksort’s known properties are safe to build on. Neither half survives contact with an actual standard library. Where introsort is the true story, it is not quicksort alone — it is quicksort switching to insertion sort below a certain size and to heapsort past a certain recursion depth, the pattern the previous section attributed to .NET’s own Array.Sort documentation. And plenty of standard libraries are not quicksort-shaped at all: Python’s own documentation names Timsort as the algorithm behind its sort, but that is a description of the current implementation, not the guarantee — the guarantee, stated separately and unconditionally, is only that the sort is stable. An introsort-based library does not make that guarantee at all; its own documentation says outright that equal elements can come out reordered.

The consequence that actually bites is stability. Code that relies on equal keys keeping their input order — sort by department, then rely on an earlier sort by hire date having survived inside each department — depends on every sort in the chain being stable, and an introsort-based one is not: its in-place partition swaps elements past each other with no regard for which one came first, so two rows in the same department can land in either order after the second sort. Recognising it starts from a mismatch: results that differ between two language runtimes on the same input, or between a debug and a release build, whenever the input has equal keys — a difference with no other plausible cause, because the input, the comparison, and the intended order are otherwise identical.

The catch is that there is no way to know which of this applies without reading the specific library’s own documentation. Some quicksort-family sorts are documented as unstable outright; some hybrids that use quicksort as one component still document a stability guarantee, because a different component of the hybrid is what carries it; and some libraries choose a fully different, stable algorithm and never touch quicksort at all. The algorithm’s name is not the checkable thing here — the stability guarantee the documentation actually states is, and it is worth reading before any code depends on an order the sort was never promised to keep.