Sorting: Count Inversions

Sorting: Count Inversions

Given n integers, count the inversions — pairs (i, j) with i < j and a[i] > a[j].

Inversions measure how unsorted an array is: sorted = 0; fully descending = n(n-1)/2. Merge sort counts them in O(n log n).

Input: line 1 n; line 2 n integers. Output: the inversion count.

Example: 5 / 2 4 1 3 5 -> 3.