5.3 Counting Inversions

Counting inversions is a problem that we face when analyzing rankings in several applications. The main challenge in this category of problems is to find a way to efficiently compare the rankings.
Let's suppose we have a sequence of n numbers a₁,a₂,a₃,…,a_n, assuming that all the numbers are different. Our concern is to find a measure that tells us how far this sequence is from being in ascending order. The value of that measure should be 0 if the list is sorted and should increase as the list gets more scrambled. Two indices i<j are inverted if a_i > a_jj, this means that a_i appears after a_j even though i<j.

Looking at every pair of numbers would take us O(n²) time.Our aim is to solve the problem in O(nlogn) time.So the algorithm we choose can not look at each inversion individually.

Algorithm Divide the problem into two lists

Merge-and-Count(A,B):

Maintain a current pointer into each list, initialized to point to the front elements

Maintain a variable count for the number of inversions,initialized to 0

While both lists are not empty:

Let a_i and b_j be the elements pointed to by the current pointer.

Append the smaller of the 2 elements above to the output list

If b_j is the smaller element:

Increment Count by the number of elements remaining in A.

End if

Advance the current pointer in the list from which the smaller element was selected.

End While