# 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.

- Author: Marcello Oliveira (https://mrcll.me/about/)
- Published: Nov 1, 2026
- Topics: ICPC, Fundamentals
- URL: https://mrcll.me/stories/counting-inversions/

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.

> Interactive figure (Inversions): open the web version at https://mrcll.me/stories/counting-inversions/

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).