Optimal inverse counting for int arrays

Question

Today I was looking for the last exam in the local computer science Olympiad, and I found an interesting problem. In short, he asks, if an integer array is given, to calculate how many inversions it has, where the inversion is a pair of indices i , j such that i > j and A[i] < A[j] . Unofficially, the number of inversions is the number of pairs that are out of order. I initially made the O(n²) solution (yes, naive), but, seeing that it would not fit the input size well, I thought about the problem a bit more and then realized that it could be done in O(n log n) time according to the merge sort option, which handles input size perfectly.

But, seeing input restrictions ( n integers between 1 and M and no duplicates), I was wondering if my solution is optimal, or do you know if there is any other solution to this problem that is superior to O(n log n) lead time?

Answer 1

The best result in the literature is the O (n √ (log n)) algorithm due to Chan and Patrascu . I do not know 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/

Answer 3

Assuming that the number of bits used to represent an integer is constant (say 32 or 64 bits), this can be solved in O (N) time.

Here is an example python implementation.

http://ideone.com/g57O87

 def inv_count(a, m=(1<<32)): if not m or not a: return 0 count = 0 ones = [] zeros = [] for n in a: if n & m: ones.append(n & ~m) else: count += len(ones) zeros.append(n & ~m) m /= 2 return count + inv_count(ones, m) + inv_count(zeros, m) 

print inv_count([1, 2, 3, 4, 5]) print inv_count([5, 4, 3, 2, 1])

We can achieve less O (N x Log (N)) time complexity, since we use the idea underlying the non-comparative radix sort algorithm to get the score.