Counting Inversions

Problem: Count pairs $(i, j)$ where $i < j$ but $arr[i] > arr[j]$.

D&C: Modify merge sort. During merge, when taking from right array, all remaining left elements form inversions.

function countInversions(arr, left, right):
    if left >= right: return 0
    mid = (left + right) / 2
    count = countInversions(arr, left, mid)
    count += countInversions(arr, mid + 1, right)
    count += mergeAndCount(arr, left, mid, right)
    return count

Time: $O(n \log n)$.