In Production · ICPC · Fundamentals
How many swaps until it is sorted?
Counting inversions is a famous problem with many known solutions. Bubblesort counts by swapping; Mergesort counts without looking at every pair.
Take [1,4,3,2] and run one pass of Bubblesort. Compare 1 and 4: leave them. Compare 4 and 3: swap. Compare 4 and 2: swap. You are left with [1,3,2,4], and one more swap finishes the job. Three swaps in total.
That is not a coincidence. Every adjacent swap undoes exactly one inversion, a pair that is in the wrong order, so the number of swaps Bubblesort makes is the number of inversions. A counter next to the swap is the whole algorithm.
It is also O(n²), which is fine for four numbers and useless for a million. Mergesort sorts in O(n log n), and it can count while it sorts. When the merge takes an element from the right half before what is left of the left half, that element jumps over every one of them, and each jump is an inversion. Add them up and you never look at a single pair directly.
Loading interactive figure…
Static version: [1,4,3,2] has 3 inversions; Bubblesort’s first pass ends in [1,3,2,4].
The count is more than a contest trick. It is a distance between two orderings, the number of pairs two lists disagree on. When a new reranker goes out and you want to know how far it moved from the old ranking, this is the number, and now you can compute it in O(n log n).