Inversion Count of an array

Given an array, find the number of inversions of it.

If (i < j) and (A[i] > A[j]) then the pair (i, j) is called an inversion of an array A. We need to count all such pairs in the array.

 
For example,

Input:  A[] = [1, 9, 6, 4, 5]
Output: Inversion count is 5

There are 5 inversions in the array – (9, 6), (9, 4), (9, 5), (6, 4), (6, 5)
 


 
Approach 1:

Simple solution would be for each element of the array, we count all elements less than it to its right and add the count to output. The complexity of this solution is O(n2).

 
C++ implementation –
 

Download   Run Code

Output:
5

 
Approach 2: (Using Merge Sort)

This is a classic problem that can be solved by merge sort. Basically for each element of the array, we count all elements more than it to its left and add the count to output. This whole magic happens inside merge function of mergesort.

Let us consider two sub-arrays involved in merge process –

inversion-count-1
inversion-count-2
inversion-count-3
inversion-count-4
inversion-count-5
inversion-count-6

 
C++ implementation –
 

Download   Run Code

Output:

5

 
Time complexity of above solution is same as that of merge sort algorithm i.e. O(nlogn).
Auxiliary space used by the program is O(n).

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂