Counting inversions
Divide and conquer: split the problem in half, solve each half, then combine. Here the combine step is a merge. Once both halves are sorted, a value taken from the right half is smaller than everything still waiting on the left, so one comparison counts all of those pairs at once.
53819274
An inversion is a pair of values in the wrong order: a bigger one before a smaller one. Count them all without checking every pair.
1function countInversions(a, lo, hi) {2 if (lo >= hi) return 0;3 const mid = Math.floor((lo + hi) / 2);4 let count = countInversions(a, lo, mid) + countInversions(a, mid + 1, hi);5 const left = a.slice(lo, mid + 1), right = a.slice(mid + 1, hi + 1);6 let i = 0, j = 0, k = lo;7 while (i < left.length && j < right.length) {8 if (right[j] < left[i]) {9 count += left.length - i;10 a[k++] = right[j++];11 } else a[k++] = left[i++];12 }13 while (i < left.length) a[k++] = left[i++];14 while (j < right.length) a[k++] = right[j++];15 return count;16}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n log n | every input: the merges always run |
| average | n log n | any input |
| worst | n log n | even reversed input, which has n(n − 1)/2 inversions |
| space | n | the copies of each half while merging |
Where it breaks
- Checking every pair. The obvious way compares all n(n − 1)/2 pairs. Pick Reversed: all 28 pairs are inversions, yet merging finds them with far fewer comparisons, because each comparison can count several pairs.
- What it measures. The number of inversions is how far an array is from sorted: 0 when sorted, n(n − 1)/2 when reversed. It is also exactly how many swaps bubble sort or insertion sort would make.
- Equal values are not inversions. The merge only counts when the right value is strictly smaller. Use
<=by mistake and equal pairs get counted too.