Today I was looking the latest exam of the local informatics olympiad and I found a interesting problem. Briefly, it asks to, given an integer array, count how many inversions it has, where an inversion is a pair of indicies i, j such that i > j and A[i] < A[j]. Informally, the number of inversions is the number of pairs that are out of order. Initially I made a O(n²) solution (yes, the naive one), but seeing it wouldn't fit well with the size of the input, I thought about the problem a bit more and then I realized it's possible to do it within O(n log n) time by a variant of merge sort, which handles good the size of the input.
But seeing the input constraints (n integers between 1 and M, and no duplicates), I was wondering if my solution is optimal, or do you know if is there any other solution to this problem that beats O(n log n) runtime?
The best result in the literature is an O(n √(log n)) algorithm due to Chan and Patrascu. No idea about the constant.