Algorithm:
Coordinate compress values to range
Process array right to left
For each element : query prefix sum up to (count of smaller elements seen)
Update position with
function countInversions(arr):
// Coordinate compress
sorted_arr = sorted unique values of arr
rank = map each value v to its 1-based position in sorted_arr
n = sorted_arr.length
bit = array of size (n + 1), filled with 0
inversions = 0
for x in arr from right to left:
r = rank[x]
// Count elements smaller than x (already processed = to the right)
inversions += query(r - 1)
update(r, 1)
return inversions
Time: . Space: .