Why does quicksort crawl on millions of status codes drawn from only ~20 distinct values?
answer
- Order is fine here; the shape is not
- How many destinations does one partition offer?
- Where do keys equal to the pivot land?
- A range that is all one value splits how?
- Give equal keys a band of their own
basics
~20 sA two-way partition gives keys equal to the pivot no region of their own, so it dumps them all on one side. With only about twenty distinct values the recursion soon hits all-equal ranges, which split one-sidedly and drive the cost toward O(n^2).
solid answer
~50 sTwo-way partitioning classifies every element as "not greater" or "greater", so keys **equal** to the pivot have no home of their own; a one-sided scan sends them all to the same side. A range where nearly every key equals the pivot then splits about `1 : m-1` — the degenerate shape, at every level. With millions of rows over roughly twenty distinct codes the recursion quickly reaches such ranges, and the cost drifts from `n log n` toward `n^2` even though the data was never sorted. The failure depends on the partition variant: a two-index scan that stops on equal keys does redundant swaps but splits near the middle. The fix is **three-way partitioning** — one pass yields a less-than region, an equal band and a greater-than region, and only the outer two are recursed into, giving expected `O(n log k)` for `k` distinct keys.
go deeper
Know that a partition step sorts elements relative to one chosen pivot value, and that elements exactly equal to the pivot have to be put somewhere — a two-way split gives them no region of their own.
Explain the arithmetic: an all-equal range split one-sidedly gives m-1 and 0, repeated down the recursion for O(m^2). Then describe the three-region alternative and why the middle band needs no further work.
Demonstrate diagnosis under production pressure: measure distinct-key count and skew rather than guessing, distinguish this from the ordered-input failure, and state which partition schemes were already immune before proposing a rewrite.
Own the tradeoff of specialising a shared sorting path for a skewed key domain: the constant-factor cost on every other caller, who maintains the extra partition variant, and whether the workload's key cardinality is stable enough to justify the specialisation.
## The diagnosis A telemetry pipeline sorts a few million request records by response status. The key domain is tiny — a couple of dozen codes, and in practice two of them cover most of the traffic. The sort was comfortable for months; volume grew, and the stage's runtime went superlinear. Nothing is sorted on arrival, no adversary is involved, and the pivot rule is the usual one. The input's *shape*, not its *order*, is the problem. ## Why equal keys hurt a two-way partition A two-way partition answers one yes/no question per element: is it on the pivot's low side or its high side? There are only two destinations, so keys **equal** to the pivot must be assigned to one of them by fiat. In the common one-sided scan, the test `a[j] <= pivot` sends every equal key into the low region. Now take a range where every key is the same value. Every element satisfies `<=`, so the low region absorbs all of them and the split is `m-1 : 0` — the maximally unbalanced shape. And this recurs: the subrange of size `m-1` is still all-equal, so it splits `m-2 : 0`, and so on. The recursion on that range costs `m + (m-1) + ... = O(m^2)`. You do not need the whole input to be one value for this to bite. With `n` records over `k` distinct keys and `n >> k`, the recursion needs only a handful of levels before subranges hold a single repeated key. From there each of those subranges is quadratic in its own size, and since a few keys dominate the distribution, the biggest of them dominates the runtime. That is the shape of the slowdown: fine for a long time, then sharply worse as `n` grows while `k` stays fixed. **Be precise: this is a property of the partition scheme, not of quicksort.** A two-index scheme that walks inward from both ends and **stops** on keys equal to the pivot swaps a matched pair and advances both — pointless-looking work that is in fact the point: on all-equal input the two indices meet in the middle, the split is even, and the range sorts in `O(m log m)`. Stopping on equal keys costs redundant swaps on ordinary data and buys immunity to this exact failure. Anyone who says flatly "duplicates kill quicksort" has skipped the mechanism. ## The fix: give equal keys their own region Three-way partitioning replaces the two-destination question with three: less than, equal to, greater than the pivot. One pass over the range produces ``` [ < pivot ][ == pivot ][ > pivot ] ``` and the recursion descends only into the outer two regions. The equal band is **finished** — every element in it is already at its final rank, because everything left of it is smaller and everything right of it is larger. That single change turns duplication from a liability into an accelerator. Each distinct key value can serve as a pivot at most once along any root-to-leaf path, because once it has been a pivot, all of its copies are removed from the problem in one step. With `k` distinct keys the recursion depth is bounded by the number of distinct values that can still be separated, and the expected cost becomes `O(n log k)` rather than `O(n log n)` — with `k = 20`, `log2 k` is under 5, so the sort is close to a handful of linear passes. On the pathological all-equal range, the first partition puts everything in the equal band and the work is a single `O(m)` pass. The price is real but small: an extra index to maintain and more element movement on inputs with few duplicates, where the equal band is usually a single element and the scheme degenerates gracefully to the two-way behaviour with slightly worse constants. That is why three-way partitioning is a targeted choice — you reach for it when you know the key domain is small or the distribution is skewed, which for status codes, country codes, enum-like categories, priority levels or boolean-ish flags you do. ## What to say in the interview Four beats, in order: 1. **Name the shape.** Millions of rows, tiny key domain, so subranges become all-equal quickly. 2. **Name the mechanism.** A two-destination partition has to dump equal keys on one side, producing the degenerate split repeatedly. This is the same `O(n^2)` failure as ordered input, reached by a different road. 3. **Qualify it.** The behaviour depends on the partition scheme; a scan that stops on equal keys is already balanced here. 4. **Give the fix and its payoff.** Three regions, recurse on two, equal band resolved once, expected `O(n log k)`. ## Two claims to keep straight - **`O(n log k)` is about distinct keys, not total size.** Doubling the number of records doubles the work; adding new distinct codes barely changes it. That is the opposite of the intuition most people bring. - **This failure is invisible to the usual defences.** Pivot-selection hardening addresses *ordering* pathologies; it does nothing here, because on an all-equal range every candidate pivot is the same value and every one of them produces the same degenerate split. If someone proposes a smarter pivot rule as the fix, they have diagnosed the wrong failure.
- Would a better pivot rule have prevented this slowdown?No, and proposing one is the classic misdiagnosis. Pivot-selection hardening fixes pathologies of ordering. On a range where nearly every key is identical, every candidate pivot is that same value, so each produces the same degenerate split. The fix has to change what the partition does with equal keys, not which key it picks.
- Where does the O(n log k) bound for three-way partitioning come from?Each distinct key can act as a pivot at most once on any root-to-leaf path, because all its copies are removed into the finished equal band in that single step. So the recursion depth is governed by how many distinct values remain separable, giving expected depth O(log k) with O(n) work per level. With twenty distinct codes that is under five levels.
- What does three-way partitioning cost on input with almost no duplicates?Slightly more than a two-way partition: an extra boundary index to maintain and more element movement, while the equal band collapses to just the pivot itself. The asymptotic behaviour is unchanged; you pay a modest constant factor. That is why it is a deliberate choice for known-skewed or small key domains rather than a universal default.
- How would you confirm this diagnosis before changing any code?Measure the key domain, not the order: count distinct keys and the frequency of the top few against total rows. Then check runtime scaling against input size — a shift from roughly linearithmic to quadratic growth as n rises while distinct keys stay fixed is the signature. Sorting a synthetic sample with the same distribution reproduces it without touching production.
Sorting mail into two bins labelled 'before M' and 'from M onwards' works badly when almost every letter is addressed to M itself — you need a third bin for M, and once it is full you are done with those letters.
saying these in an interview costs you the question
- Says duplicates are irrelevant because the values compare equal anyway
- Blames input ordering when the input was never ordered
- Proposes a smarter pivot rule as the fix for all-equal ranges
- Claims all partition schemes degrade identically on duplicates
- Thinks the equal band still has to be recursed into
- Assumes O(n log k) depends on total row count rather than distinct keys