arrays - calculating the number of “inversions” in a permutation

Question

Let A be an array of size N. we call a couple of indexes (i,j) an "inverse" if i < j and A[i] > A[j]

I need to find an algorithm that receives an array of size N (with unique numbers) and return the number of inverses in time of O(n*log(n)).

Answer 1

You can use the merge sort algorithm.

In the merge algorithm's loop, the left and right halves are both sorted ascendingly, and we want to merge them into a single sorted array. Note that all the elements in the right side have higher indexes than those in the left side.

Assume array[leftIndex] > array[rightIndex]. This means that all elements in the left part following the element with index leftIndex are also larger than the current one in the right side (because the left side is sorted ascendingly). So the current element in the right side generates numberOfElementsInTheLeftSide - leftIndex + 1 inversions, so add this to your global inversion count.

Once the algorithm finishes executing you have your answer, and merge sort is O(n log n) in the worst case.