Problem 44
Description
This problem was asked by Google.
We can determine how “out of order” an array A is by counting the number of inversions it has. Two elements A[i]
and A[j]
form an inversion if A[i] > A[j]
but i < j
. That is, a smaller element appears after a larger element.
Given an array, count the number of inversions it has. Do this faster than O(N^2)
time.
You may assume each element in the array is distinct.
For example, a sorted list has zero inversions. The array [2, 4, 1, 3, 5]
has three inversions: (2, 1)
, (4, 1)
, and (4, 3)
. The array [5, 4, 3, 2, 1]
has ten inversions: every distinct pair forms an inversion.