Top-k becomes a user-tunable parameter up to the full catalog — which selection strategy do you commit to?

## What actually changes when k is no longer tiny Every comfortable claim about selection assumes `k << n`. Track each one as `k` grows toward `n`: **The retained-candidate scan.** Time O(n log k) — but `log k` approaches `log n`, so the bound converges on the full sort's O(n log n). Space O(k) approaches O(n), so the memory argument that justified it disappears. Its per-record work is a comparison plus an occasional sift, with scattered memory access; a good library sort over a contiguous buffer has excellent locality. Long before the asymptotics converge, the measured curves cross. **Quickselect.** Expected O(n) *independent of k* — the partition-and-narrow structure does not care where rank `k` sits. This is the region where quickselect genuinely shines, e.g. "give me the cheaper half of the catalog." The costs do not go away: it permutes the caller's buffer, it needs the whole input resident, and its worst case under naive pivots is O(n^2). It also hands back an unordered prefix. **The full sort.** O(n log n) regardless of `k`, and it is the only option that delivers a ranked result with no follow-up work. When `k` is large, the post-selection ordering step the others need — O(k log k) — stops being negligible and starts approaching the sort you were avoiding. ## The crossover is measured, not derived There is no universal `k/n` threshold. It depends on record size, comparator cost, memory hierarchy, and how well the sort exploits pre-existing order — an adaptive merge-based sort runs close to O(n) on already-ordered runs, which a price export very often is. The defensible engineering answer is to benchmark the two or three candidates against real records at several `k` values and pick a threshold from the curves, then keep the benchmark so the threshold can be re-derived when hardware or data changes. Presenting a crossover as a derived constant is the tell of someone who reasoned only on paper. ## The part that makes it a leadership call The technical answer is only half of it. A tunable `k` is a promise to the user that any `k` is supported, and it lands in code somebody else maintains: - **How many code paths?** Three tuned strategies behind one function is three times the surface for a subtle bug, and the bug will be in the branch nobody exercises. Two paths with an explicit, named threshold is usually the right trade; a single path is better still if the profile allows it. - **What does the interface promise?** If the result is documented as "the k cheapest, in price order," you have committed to the ordering step in every path — and made the sort branch strictly simpler than the alternatives at large `k`. If it is documented as "the set of the k cheapest, unordered," you have kept the cheap paths but pushed work onto callers who will each re-sort it, badly. - **What is the supported range?** A tunable that accepts k = n implies the service can return 10 million records. Memory ceilings, response sizes and timeouts all argue for a published maximum, pagination, or an asynchronous export path — that is a product boundary, not an algorithm choice. - **Which risk do you accept?** In a per-request path, an expected-linear method with a quadratic tail trades a better median for a worse tail. If the SLA is written on the tail, the bounded method wins even though it loses on average. In an offline batch, a rare slow run is cheap and the average is what you are paying for. ## A defensible recommendation 1. One public entry point taking `k`, documented as returning the k cheapest **in price order** — because that is what the product will ask for eventually anyway, and it makes the branches comparable. 2. Below a measured crossover, the single-pass retained-candidate scan plus an O(k log k) ordering of the result; above it, sort and slice. 3. A published maximum `k`, with anything beyond it served by pagination or an offline export. 4. Quickselect only if profiling on real traffic shows a specific mid-range of `k` where it pays for its preconditions — and only where the buffer is ours to permute. 5. The benchmark checked in next to the threshold, so the number can be re-justified rather than inherited. ## The register that lands "I would not ship three strategies. As k grows the heap's advantage disappears — log k becomes log n and the state becomes O(n) — so I would measure the crossover on real records, run the scan below it and a plain sort above it, publish a maximum k with pagination beyond that, and document that the result comes back ranked. Quickselect earns a place only if the profile shows a k range where it wins and the buffer is ours to disturb."