Count Inversions ​
Count Inversions — GeeksforGeeks
Count the pairs (i, j) with i < j and arr[i] > arr[j] — i.e. how many pairs are out of their sorted order.
Approach ​
Merge sort with modification. While merging, if arr[i] > arr[j], then count += mid - i + 1. Do this, and return up from each recursion tree