When would you reject cyclic sort for a missing-token audit and reach for something else?

## The question behind the question An interviewer who asks when you would *not* use this pattern is not testing recall of the swap loop. They are testing whether you check preconditions before reaching for a technique — the failure mode being a candidate who pattern-matches "find the absent value" to "cyclic sort" and starts writing swaps before asking what the values look like or who else owns the buffer. ## The three-part license **A dense bounded range with one slot per candidate.** The pattern works because a value *is* an address. That requires every candidate value to map to a real slot. Seat tokens numbered `1..n` in a pile of `n` qualify. Booking references, account identifiers, or anything drawn from a wide sparse space does not: the home index computed from such a value is not a slot you own. Sometimes the range can be *manufactured* — if the audit is over a contiguous window of identifiers with a known base, subtract the base and you are back in range. If the values are sparse within their bounds, you are not, because the slot count no longer matches the candidate count. **Permission to mutate.** The pattern reorders the caller's buffer destructively. A read-only region, a memory-mapped view of a file, or a buffer handed to you with an explicit no-mutation contract all rule it out outright. **Exclusive access, and no downstream dependence on order.** Even where mutation is legal, it may be wrong. If the arrival order carries meaning — the scan sequence is itself part of the audit trail — reordering destroys evidence. If anything else can read the buffer while you work, a destructive in-place shuffle is an even worse idea. "Technically mutable" and "safe to scramble" are different claims, and a senior answer separates them. ## What to reach for instead | Situation | Alternative | Cost | | --- | --- | --- | | Range bounded, mutation forbidden | Auxiliary presence bitmap over the range | O(n) time, one bit per candidate | | Identifiers sparse or unbounded | Hash-based membership set | O(n) expected time, O(n) space, O(n) worst case per lookup under collisions | | Caller wants an ordered result anyway | Ordinary comparison sort, then walk for gaps | O(n log n), and it mutates too | | Input arrives as a one-pass stream | Neither — you need a streaming formulation | Depends on what you may retain | Be precise about the hash option. Expected constant-time membership is not a guarantee: with adversarially chosen keys or a weak hash, lookups degrade to linear, and the space overhead is real. It is the right answer for sparse identifiers, not a strictly better answer. ## "Why not just sort it?" This is the standard probe, and the honest reply has two halves. First, sorting works and is the sane default when you have no special structure to exploit — but it costs O(n log n), and comparison-based sorting cannot do better, because it learns about the input only by comparing elements to each other. Cyclic sort refuses to play that game: it reads a value and computes an address, which is information the comparison model never had, so the linear bound is not a contradiction of anything. Second — and this is the part weak answers miss — sorting is *also* destructive. If your objection to cyclic sort was mutation, sorting in place does not rescue you; you would have to copy first, and now you are spending O(n) extra space anyway, at which point the bitmap or the membership set is the better trade. ## The constraint conversation to have out loud Before committing, ask four things: what range do the identifiers span, may I modify the buffer, does anything downstream depend on its current order, and does the caller need the result ordered? Those four answers select the technique deterministically. Volunteering them is what separates the senior answer from the memorised one — and if the interviewer says the buffer is read-only after you have already written the swap loop, you have failed the actual test. ## Scale and the honest tradeoff At small `n` none of this matters much; the constants dominate and every option is instant. The trade sharpens when the buffer is large and memory is tight — cyclic sort's O(1) auxiliary space is genuinely valuable there, and its scattered access pattern is genuinely a cost. State both. The pattern is not free speed; it is a specific trade of the caller's data ordering for constant extra space, available only when the input's shape licenses it.