Finding the 100 cheapest of 10 million products: sort, size-k heap, or quickselect?
answer
- How much of the answer do you need?
- Compare k against n first
- Three costs, three side effects
- One pass, bounded state, untouched input
- log k vs log n, and who mutates
basics
~20 sSorting the whole catalog costs O(n log n) to answer a question about 100 items. A retained-candidate heap does one pass in O(n log k) with O(k) memory; quickselect averages O(n) but rearranges the input and needs it all resident.
solid answer
~50 sThree costs, three side effects. A full sort is O(n log n) and hands back a ranked catalog you did not ask for — though it is the only one that returns the 100 in price order for free. A retained-candidate heap is O(n log k) time and O(k) extra space, reads the input without touching it, and works in one pass: at k = 100 and n = 10,000,000, `log k` is about 7 against `log n` of about 23. Quickselect is expected O(n), the best on paper, but O(n^2) worst-case under naive pivots, and it permutes the caller's records in place while needing the whole input resident. So: heap if the input streams past or must not be disturbed, quickselect if the data sits in a buffer you own and you need only the set, full sort if the ranking is wanted anyway.
go deeper
Be ready to give the three costs from memory — O(n log n) for a full sort, O(n log k) for a bounded candidate heap, expected O(n) for quickselect — and to say why sorting 10 million for a 100-item answer is wasteful.
Explain where each cost comes from: one comparison-based pass with a k-sized structure, versus ordering everything, versus recursing into a single partition. Name the extra space each needs and which of them rearranges the caller's data.
Show that you pick by constraints, not by the asymptotic winner: input residency, ownership of the buffer, whether ranking was actually requested, and what the measured crossover is on real hardware rather than on paper.
Own the question of how many selection code paths the codebase should carry. Three tuned strategies behind one interface is a maintenance cost; defend a single documented default with a measured threshold instead.
## The task, stated precisely You have 10,000,000 product records, each carrying a decimal price, and you must report the 100 with the lowest price. `n` is 10,000,000; `k` is 100. Note how lopsided that is: `k` is one hundred-thousandth of `n`. Almost every interesting property of the three standard answers comes from that ratio. ## The three approaches **Full sort.** Order all `n` records by price, take the first `k`. Time O(n log n) for any comparison sort. You get a ranked result — the 100 come out cheapest-first — and you also get 9,999,900 orderings nobody asked for. **Retained-candidate heap.** Keep a bounded collection of the best `k` seen so far, structured so the *worst* of those candidates is instantly visible; scan the input once, and each record either loses to that worst candidate and is dropped, or displaces it. Time O(n log k), extra space O(k), input untouched, single pass. **Quickselect.** Repeatedly partition the buffer around a pivot and recurse into only the side that contains rank `k`. Expected time O(n), worst-case O(n^2), auxiliary space O(1) beyond the input — but it *rearranges the input* and needs the whole thing addressable. (A fourth, often-forgotten option: build a heap over all `n` items bottom-up in O(n), then extract `k` times for O(n + k log n). For tiny `k` that is essentially linear and competitive with quickselect — but it needs O(n) space for the heap, or it mutates the input to heapify in place. It sits on the same memory/mutation axis as the other three.) ## The cost table | Approach | Time | Extra space | Touches input? | Output ordered? | Works on one pass? | |---|---|---|---|---|---| | Full sort | O(n log n) | O(1)–O(n) by algorithm | Yes, reorders it | Yes, ranked | No | | Size-k heap | O(n log k) | O(k) | No, read-only | No, unordered set of k | Yes | | Quickselect | O(n) expected, O(n^2) worst | O(1) | Yes, permutes it | No, unordered prefix | No | ## Reading the asymptotics honestly O(n log k) versus O(n log n) is not a change of order — both are `n` times a logarithm. What changes is the logarithm's size and, more importantly, the *memory*: 100 retained candidates instead of 10,000,000 records. On a machine where 10M records do not fit comfortably, that is not a constant factor, it is the difference between working and not working. And O(n) expected is an *average over pivot choices*, not a promise about the call you are about to make. Big-O here is an upper bound on a model, not a measurement: the sort may well beat quickselect at n = 1,000 because its constants are smaller and its memory access is friendlier, which is exactly why mainstream library sorts drop to insertion sort on short runs. ## What actually decides it 1. **Do you own the buffer?** Quickselect permutes it. If the caller's order matters, you must copy first — and that copy is O(n) time and O(n) space, which erases most of quickselect's advantage. 2. **Does the input fit, and does it arrive all at once?** Sort and quickselect are *offline*: they need everything, with random access. The heap is *online*: it sees each record once. 3. **Did the requirement ask for a ranked list?** Only the sort gives ordering for free. The other two hand you an unordered group of 100; ordering them afterwards costs O(k log k), which at k = 100 is nothing — but say so explicitly rather than pretending the heap emits a ranking. 4. **Is `k` really small?** Everything above assumes k << n. When `k` grows toward `n`, the heap's advantage evaporates and the sort's simplicity starts to win. ## An ecosystem aside The decision does not arrive the same way everywhere: some standard libraries (C++'s, for instance) ship an average-linear partial-selection routine right next to the full sort, while others (Java's and Go's among them) offer only complete sorts, so reaching for selection means writing or importing it. Same three algorithms, different defaults — which is a reason to know the tradeoff rather than the library entry. ## The register that lands "Sorting 10 million to report 100 is doing 10 million records' worth of ordering work for a 100-record answer. I would scan once keeping the best 100 — one pass, 100 items of state, input untouched. If the data is already in a buffer I own and I only need the set, quickselect is faster on average, and if the product wants a ranked list anyway, just sort."
- The product team wants the 100 displayed cheapest-first. Does that change your recommendation?Not much, but say it out loud. The heap and quickselect both return an unordered group of k; ordering it afterwards is O(k log k), which at k = 100 is trivial next to a 10-million-record scan. It only changes the answer when k grows large enough that k log k stops being negligible — at which point you are close to just sorting everything and getting the ranking for free.
- Why not always take quickselect, since expected O(n) is the best of the three?Because expected O(n) is an average, not a per-call guarantee: with naive pivot rules, sorted or duplicate-heavy input degrades it to O(n^2). It also permutes the caller's records in place and needs the whole input resident with random access, so it is unusable on a stream and needs an O(n) copy whenever the original order matters.
- At what point does the sort simply become the right call?When n is small enough that the difference is noise, when the ranking is part of the requirement, or when k is a large fraction of n so that O(n log k) and O(n log n) converge. Also when maintainability wins: one obvious sort that a whole team reads correctly can be worth more than a selection routine that is faster on a graph.
Picking the hundred shortest people at a stadium: you do not line all fifty thousand up by height — you walk the rows holding a mental shortlist of a hundred and swap out your tallest whenever someone shorter walks by.
saying these in an interview costs you the question
- Sorting everything and slicing k, without noticing the waste
- Calling the size-k heap approach O(n) instead of O(n log k)
- Claiming quickselect is O(n) with no worst case
- Assuming the heap hands back a ranked top-k
- Ignoring that quickselect reorders the caller's data
- Treating O(n log k) as a different complexity class from O(n log n)