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.