Why sort unmatched refund records first when every scan you replace is only linear?

## Sorting is a precondition, not a result In the optimize phase, "sort first" looks like paying more to get less: you replace an `O(n)` scan with an `O(n log n)` sort. The defence is that you are not replacing the scan - you are changing what every subsequent step is allowed to assume. Sorted input is a **monotonicity guarantee**, and a whole family of cheap techniques is unlocked by it and unavailable without it. What order buys, concretely: - **Adjacency of equal keys.** Records that must match each other end up next to each other, so a nested `O(n^2)` scan becomes a single linear sweep with two cursors. - **Searchability.** A sorted sequence supports binary search at `O(log n)` per probe, provided the structure gives random access - binary search needs both a sorted (or monotone) domain *and* the ability to jump to the middle, which a sequentially linked structure does not offer. - **Detectable duplicates and gaps.** Repeats become runs; missing values become jumps. Both are single-comparison checks in a sweep. - **Meaningful early exit.** Once the key you are scanning past can no longer match, you stop. That pruning is only sound because order guarantees nothing better comes later. ## The arithmetic that settles the argument Let k be the number of times you would otherwise scan. | approach | cost | |---|---| | rescan per question | O(k*n) | | sort once, then probe | O(n log n + k log n) | | sort once, then one sweep | O(n log n + n) | Sorting wins once `k` grows past about `log n`, which for realistic sizes is a very small number - a handful of queries is usually enough to justify it. Say this out loud with the variables named; "sorting is better" without the crossover is an assertion, while the comparison is an argument. ## When sorting first is the wrong call A skeptic's objection is sometimes correct, and knowing when is the senior half of this answer: - **One-shot work.** If a single pass answers the whole question, an `O(n)` scan beats `O(n log n)` outright. Sorting to answer one question is the mirror image of the "optimize the wrong term" mistake. - **Small n.** Asymptotics promise nothing at small sizes; a linear scan over a few dozen records is faster than sorting them, which is the same reasoning that makes mainstream sorts hand small runs to insertion sort rather than recursing. - **Streaming or unbounded input.** Sorting requires the whole input in hand; if records arrive continuously you cannot buffer, order is not available at any price. - **Arrival order is part of the answer.** Sorting destroys the original sequence unless the comparison is on a key that preserves what you need, the sort is stable, or you carry an explicit position with each record. Stability is a narrow promise - it preserves relative order among **equal** keys only - so if you need the original order of *unequal* records restored, stability does not give it to you; the position field does. - **The key you can sort by is not the key you must match on.** Matching on several independent attributes at once cannot be linearized by one ordering, and sorting by the wrong one buys nothing. - **Moving records is expensive.** Large records, or a structure without random access, change the constants enough to matter; sorting an index or a set of keys instead of the payload is often the fix. - **You only need equality, not order.** Bucketing records by key is expected linear and skips the log factor. It gives up ordered iteration and its guarantee is expected rather than worst-case - adversarial or badly distributed keys degrade it - so the choice is order and worst-case predictability versus expected-linear speed. ## Defending it to a reviewer A good defence has three parts, in this order: the **guarantee** you bought ("after this, equal amounts are adjacent, so matching is one sweep"), the **arithmetic** ("we answer this thousands of times per report, so `k` is far past `log n`"), and the **conditions under which you would remove it** ("if this became a single-query path, or if records started streaming, I would go back to the scan"). Naming your own exit condition is what separates a considered optimization from a habit. ## The verification obligation Sorting first also changes what can break. Ties are the classic one: two records with equal keys can appear in either order under an unstable sort, so any downstream step that assumed the earlier-arriving record comes first is now nondeterministic - a defect that reproduces intermittently and is miserable to chase. Before declaring the optimization done, trace a small example containing a tie and confirm the result does not depend on which of the two came out first.