Problem:

You are given an array of N numbers. You are to find the number of pairs of numbers in the array s.t a[i] < a[j].

Solution:

First you find the set of all distinct elements in the array {x(1), …, x(M)} with x(i) < x(i+1) and their corresponding counts {c(1),…,c(M). Now it is easy to see that the required number of such pairs is

Sum_{i} (c(i) * (c(1)+…c(i-1))

This is simply

Sum_{i} (c(i) * c_cumulative(i-1))

where c_cumulative(k) is the cumulative sum of c() that can be computed in O(M) time. Thus, the total counts of such pairs can be computed in O(N).