# 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.

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.

• The parity of the number of inversions is the sign of the permutation that brings to array to sorted form. The sign of a permutation is also the parity of the length of (some/every) expression of the permutation as a product of transpositions. So, yes, a single swap changes the parity of the number of inversions, and a fortiori the number itself. Mar 6, 2015 at 12:35
• 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
• @EmilJeřábek: Yes, thank you. I proved this by counting number of inversions, but yours is much simpler. Mar 6, 2015 at 17:07
• @domotorp: I assumed that this was more or less obvious. Mar 6, 2015 at 17:08