How to find the number of inversions in an array ?

Posted by Michael on Stack Overflow See other posts from Stack Overflow or by Michael
Published on 2010-12-29T08:32:53Z Indexed on 2010/12/29 8:54 UTC
Read the original article Hit count: 190

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:

  1. 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.
  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 ?

© Stack Overflow or respective owner

Related posts about arrays

Related posts about algorithm