Count Inversions
Count pairs (i, j) with i < j but nums[i] > nums[j] — how far the array is from sorted.
Intuition
During a merge of two sorted halves, the moment you take an element from the right half before elements remain in the left half, that right element is smaller than all remaining left elements — that's a whole batch of inversions counted in one step.
Counting inversions is merge sort with one extra line. During the merge, when a right-hand element is placed before left-hand ones, it is smaller than every remaining left element — so it forms that many inversions at once. Recognising that a sorting algorithm's structure can carry a side computation is the transferable idea.
Approach
Recurse on halves
Inversions = inversions inside left + inside right + cross inversions. The first two come from recursion.
Count during merge
Merging sorted halves: when right[j] < left[i], it jumps ahead of len(left) − i left elements — add that many inversions at once.
Why it's fast
Each merge is linear and there are log n levels → O(n log n), versus O(n²) brute force.
Solution & live demo
Common pitfalls
Counting one inversion per merge step
else:
inv += 1
merged.append(right[j]); j += 1else:
inv += len(left) - i
merged.append(right[j]); j += 1The left half is sorted, so if right[j] beats left[i], it also beats everything after left[i]. Counting one at a time misses that whole block and reduces the algorithm to a wrong O(n log n) undercount.
Using < and counting equal values as inversions
if left[i] < right[j]:
if left[i] <= right[j]:
An inversion requires a strictly greater element preceding a smaller one, so equal values are not inverted. Strict < sends ties down the counting branch and inflates the total.
Dropping the child counts
merged, inv = [], 0
left, x = sort(a[:mid]) right, y = sort(a[mid:]) merged, inv = [], x + y
Inversions accumulate from three sources: those entirely inside the left half, inside the right half, and those crossing between them. Resetting to zero keeps only the crossing pairs.
Edge cases
Right elements never jump ahead → 0 inversions.
Every pair inverts: n(n−1)/2, counted in batches.