For counting the number of inversions in an array, there are many $O(n \log n)$ algorithms, e.g. the one that modifies Merge Sort. There is an easy $\Omega(n)$ lower bound simply because you have to look at all the elements. I saw some faster algorithms in the RAM model, such as this $O(n \sqrt{\log n})$ algorithm for a permutation on $n$ elements: http://people.csail.mit.edu/mip/papers/invs/paper.pdf. Is anything else known in the comparison model for inversion counting? I'm mainly curious if there are better lower bounds.
Lower bounds for inversion counting in comparison model?
ds.algorithms;lower bounds
I'm not totally sure, but it seems you can get $\Omega(n \log n)$ lower bound.Suppose in the worst case we use $o(n \log n)$ queries. Consider a decision tree for our algorithm. Cause of depth of the tree there should be a leaf such that there are at least two permutations which correspond to it.Now consider all queries with answers on a path from the root to the leaf. We know that they set a partial, not total, order. Consider two elements, which can not be compared. Take any permutation, which corresponds to this order, and swap these elements.I don't have a strict proof, but it seems to be true, that after such a swap number of inversions should be changed. If so, we broke our algorithm and obtained lower bound.