Count of inversions in array is a textbook showcase of what is the difference between quadratic and linearithmic algorithm.

While naive method may select each tuple of items to be compared, more efficient approach is to adapt merge-sort to do the counting…