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

Once one list is empty, append the remainder of the list to the output

Return Count and the merged list.

The total running time of this algorithm is O(n) time.For solving the problem,we simultaneously sort and count as follows:

Sort-and-Count(L)

if list L has one element

return 0 and the list L

Divide the list into two halves A and B

(i_A, A) = Sort-and-Count(A)

(i_B, B) = Sort-and-Count(B)

(i, L) = Merge-and-Count(A, B)

return i = i_A + i_B + i and the sorted list L

For a list with n elements, the overall running time is O(nlogn).
I give this section 8/10