## Counting the number of inversions in a list

Given an array of numbers, how do we count the number of inversions in it? An inversion is an ordered pair if indices (i,j) such that i < j and A[i] > A[j] . For example consider the array {3, 2, 1, 5, 4} The inversions are {(0,1), (0,2), (1,2), (3,4)} totaling 4. We can…