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: Naive

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

Download   Run Code

Java

Download   Run Code

Output:

Inversion count is 5

 

Approach 2: (Using Merge Sort)

This is a classic problem that can be solved by Merge Sort Algorithm. 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

 
Below’s C and Java program that demonstrates it:

C

Download   Run Code

Java

Download   Run Code


Output:

Inversion count is 5

 
Time complexity of above solution is same as that of merge sort algorithm i.e. O(nlogn) and 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 🙂
 


Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Michael
Guest
Michael

nice..

arandomguy
Guest
arandomguy

Please add another approach using binary indexed tree (BIT).