Find the Inversion Count of an Array [ Microsoft, Flipkart]

Problem:

Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.

Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j. [Courtesy: geeksforgeeks.org]

Problem Link

Solution:

The problem can be solved using O(n^2) algorithm like bubble sort.

• This way just perform the bubble sort on the array.
• Each time inside the loop we find a comparison between a pair that require a swap to sort, increase Inverse_Count value.
• Finally print the value of Inverse_Count.

Another approach is to use Merge Sort , an O(nlogn) algorithm.

Merge sort use two sorted array and merge these two into a bigger array. So to solve the problem using merge sort we need to do as follows:

• Let the two arrays to be merged are Left and Right array.
• If we find an element in Right array that should go before the current comparing element of Left array, than it is obvious that rest of Left array elements will go after that element of the Right array. So from here we can say  Inverse_Count  will  be increased to Inverse_Count+(Length Of the Left Array- Current Element Index).

The problem appeared as interview Question in: Microsoft, Amazon, Adobe, FLipkart.