Why does quickselect degrade on millions of ratings drawn from only five distinct values?

## The data shape that breaks the usual reasoning A rating field with values 1 through 5, an enum-valued column, a bucketed score: these are collections of millions of elements over a domain of a handful of keys. Every intuition about pivot randomisation was built for a model where ties are rare, and it quietly fails here. Randomising the pivot protects you against an adversary who controls the *arrangement* of the data. It does nothing about a key domain so small that the pivot ties with a fifth of the collection no matter which position you draw it from. ## Why a two-way partition stalls A Lomuto-style partition walks one index forward and maintains a boundary, moving every element that compares as "not greater than the pivot" to the left region. On a range where every element equals the pivot, every element moves left, the pivot's final index lands at one end, and the surviving range shrinks by exactly one. Repeat that over a run of a million identical ratings and the summed work is the arithmetic series `n + (n-1) + ...`, which is quadratic. The failure looks identical to the sorted-input pathology, but its cause is different and the usual remedy does not apply: you cannot randomise your way out of ties. Hoare-style partitioning behaves noticeably better on the same data, because both scanning pointers stop when they meet an element equal to the pivot and swap across. Equal elements therefore end up distributed on both sides and the split lands near the middle, which restores a geometric shrink. It still does redundant work, though: it keeps re-partitioning elements it already knows are equal to a pivot it already examined. ## The three-way partition The direct fix is to make equality a first-class outcome. A three-way scheme maintains three regions in one pass: strictly less than the pivot, equal to it, and strictly greater. It ends with an explicit equal range `lt..gt`. That range changes the selection logic in two useful ways. - **Immediate termination.** If the wanted index `k` lands anywhere in `lt..gt`, the answer is the pivot value itself, and the routine returns without any further recursion. On a five-valued rating column, the median almost always lands in the largest equal run, so the routine typically finishes on the first or second pass. - **Whole-class elimination.** When `k` falls outside the equal range, the recursion drops not just one element but every occurrence of that key. Since the recursion can therefore eliminate at least one distinct value per round, the number of rounds is bounded by the number of distinct keys, and with five keys the total is a small constant number of linear passes. The cost is a slightly busier inner loop: three comparisons and two moving boundaries instead of one. On data with all-distinct keys that overhead is real and usually not worth paying, which is why three-way partitioning is a targeted choice for low-cardinality data rather than a universal default. ## Diagnosing it in production The signature is a job whose runtime is fine on a sample and catastrophic on the full dataset, scaling like the square rather than linearly, with a profile dominated by the partition loop and no obvious hot allocation. A quick check is to count distinct keys: if the cardinality is tiny relative to the element count, ties are the suspect. Two other observations help. First, the answer to a selection query over a five-valued domain is one of five values, so a counting pass over the value domain answers it in a single scan with no partitioning at all, and on a known small key range that is the simplest fix of all. Second, an equal-heavy dataset makes the *result* less interesting than the interviewer's framing suggests: when the median rating is 4, what the analyst usually wants next is the distribution, which the counting pass already produced. ## What to say out loud Name the mechanism, not just the symptom: the surviving range must shrink by a constant *fraction*, and a two-way partition over a run of equal keys shrinks it by a constant *count*. Then name the fix in order of preference for the workload: three-way partitioning when keys are few but the domain is unknown or unbounded, and a plain counting pass when the key domain is small and known in advance.