Why can selection sort reorder equal-comparing records when it performs only n-1 swaps?

## Why swap count and equal-key order are the same story Selection sort's headline property is that it writes very little: one swap per pass, at most n-1 for the whole run, regardless of input. That economy comes from doing all the work with comparisons and then making a single, arbitrarily long jump. The jump is the problem. Preserving the relative order of records that compare equal — the property usually called stability — is destroyed exactly by moves that carry an element across other elements it does not compare unequal to. ## The mechanism, concretely ``` for i in 0..n-2 m = i for j in i+1..n-1 if a[j] < a[m] m = j swap(a[i], a[m]) ``` The scan is careful: with a strict `<`, `m` keeps the *first* minimum it saw, so ties during the scan are handled conservatively. That is not where order is lost. Order is lost in the final line. `swap(a[i], a[m])` does two things: it moves the minimum into place (fine) and it evicts whatever was at `a[i]` all the way out to position `m` (not fine). That evicted element has just been carried past every element between `i` and `m`, including any that compare equal to it. Trace inventory rows keyed by price, listed in arrival order: | step | array | |---|---| | start | (5, #1), (5, #2), (2, #3) | | pass i=0: minimum is (2, #3) at index 2, swap with index 0 | (2, #3), (5, #2), (5, #1) | | pass i=1: minimum of the rest is (5, #2), already at index 1 | (2, #3), (5, #2), (5, #1) | The result is correctly sorted by price. But #1 arrived before #2 and now sits after it. Nothing compared the two prices as unequal; the eviction alone did it. Three records are enough to demonstrate the defect, which makes this a good whiteboard answer — you can produce the counterexample in ten seconds. ## Why this bites in practice The damage is invisible at the point of the swap. The output is sorted by the key you asked about, every assertion on that key passes, and the corruption only shows up downstream where something depended on the secondary order — a display that showed oldest-first within a price band, a batch that processed ties by arrival, a diff that now churns because ties come out differently on every run. That last one is nasty: run-to-run instability in output ordering looks like a data problem, not a sort problem. A second trap: people assume equal keys are interchangeable. They are interchangeable only when the records are *identical*, which is rarely true — records usually carry payload beyond the sort key, and that payload is what makes the reordering observable. ## Can you fix it? Yes, and the fix is instructive because of what it costs. Replace the swap with a rotation: shift the block from `i` to `m-1` one position right, then drop the minimum into slot `i`. No element ever crosses an equal-keyed element, so relative order of ties survives. The price is that a single pass may move O(n) elements, giving O(n^2) total data movement instead of n-1 swaps. Selection sort's one genuine advantage — minimal writes — is gone, and you are left with a quadratic sort with no compensating property. So the honest framing for an interview: selection sort trades equal-key order for write economy. If you need equal-key order preserved, either keep the sort that gave it to you, or make the key total by folding the tiebreak field into the comparison so that no two records compare equal in the first place. ## The contrast with adjacent-exchange bubbling Bubble sort, if it swaps only on a strict greater-than between neighbours, never exchanges two elements that compare equal and never moves an element across a non-neighbour. Equal keys therefore cannot cross, and relative order survives. Note the fragility: change the comparison to `>=` and the same algorithm starts swapping equal neighbours, and the property is gone. It is one character. ## Common wrong answers - "Fewer swaps means less disturbance, so it is the safer substitute." The opposite: fewer, longer swaps are what disturb equal keys. - "Only adjacent swaps can break relative order." Adjacent swaps of *equal* elements break it; long-range swaps break it much more readily. - "Selecting the first minimum makes it order-preserving." The scan is conservative; the eviction is not. - "Equal keys are interchangeable, so it cannot matter." Only if the records are identical, which they usually are not.