THE INVERSION COUNT how unsorted is it? — count the out-of-order pairs
An inversion is a pair of positions i < j where a[i] > a[j] — a pair that is out of order. The inversion count measures exactly how far an array is from sorted: zero means already sorted, and the maximum n(n−1)/2 means reversed. It is the number of adjacent swaps bubble sort would make, the Kendall tau distance between rankings in statistics, and — beautifully — merge sort can count all inversions for free in O(n log n) while it sorts, since each merge tallies the cross-pairs it fixes. [2,4,1,3,5] has 3 inversions: (2,1), (4,1), (4,3).
THE TECHNIQUE count pairs i<j with a[i]>a[j] — 0 sorted, n(n−1)/2 reversed
The demo counts the inversions of [2,4,1,3,5] — 3 out-of-order pairs — and confirms a sorted array has 0: live demo
HISTORY & CREDIT inversions · Kendall tau distance
“Sorted-ness is all-or-nothing.” — the inversion count measures it exactly, from 0 (sorted) to n(n−1)/2 (reversed). cited
the pair · an inversion is i < j with a[i] > a[j] — out of order. the measure · 0 = sorted, n(n−1)/2 = reversed; the adjacent-swaps bubble sort needs. the trick · merge sort counts all inversions for free in O(n log n) while sorting — Kendall tau.
A single number for how far from order an array is — the out-of-order pairs, counted. measure
RECOMMEND FOR I-13 the out-of-order pairs, on the compiler
On the canonical compiler, [2,4,1,3,5] has 3 inversions, and the sorted [1,2,3,4,5] has 0:
Recommend as the batch’s close — a NULL, a measure. The inversion count is a computed measure of disorder (B39), forall-pinned by the array; merge sort computes it as a byproduct (a resource nicety, B40). No new invariant. NULL — and a fitting end to THE ORDER: a single number for how much order is missing, from 0 to fully reversed.