Optimal inversion counting on int arrays

Question

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?

Answer 1

The best result in the literature is an O(n √(log n)) algorithm due to Chan and Patrascu. No idea about the constant.

Answer 2

O(n log n) is the best as far as I know.

A detailed explanation was given here:

http://www.geeksforgeeks.org/counting-inversions/