# Lower bounds for inversion counting in comparison model?

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.

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.
• You are using (without explicitly stating) that in any partial order for any two incomparable elements, $x$ and $y$, there are two possible extensions that differ only in $x$ and $y$ being swapped. This is indeed true; If every element smaller than $x$ or $y$ is smaller than them, every other element bigger, then we can swap $x$ and $y$. Mar 6, 2015 at 14:26