How to find the number of inversions in an array ?
- by Michael
This is an phone interview question: "Find the number of inversions in an array". I guess they mean O(N*log N) solution since O(N^2) is trivial.
I guess it cannot be better than O(N*log N) since sorting is O(N*log N)
I have checked a similar question from SO and can summarize the answers as follows:
Calculate half the distance the elements should be moved to sort the array : copy the array and sort the copy. For each element of the original array a[i] find it's position j in the sorted copy (binary search) and sum abs(i - j)/2.
Modify merge sort : modify merge to count inversions between two sorted arrays (it takes O(N)) and run merge sort with the modified merge.
Does it make sense ? Are there other (maybe simpler) solution ? Isn't it too hard for a phone interview ?
