# Counting inversion pairs

A classic application of divide and conquer is to solve the following problem:

Given an array $a[1\dots n]$ of distinct, comparable elements, count the number of inversion pairs in the array: pairs $(i,j)$ such that $a[i] \gt a[j]$ and $i \lt j$.

One approach to this is to do a Merge Sort, but also counting of the number of inversion pairs in the sub-problems. During the merge step, we count the number of inversion pairs that span across the (two) sub-problems and add to the counts of the sub-problems.

While this is good, and gives an $O(n\log n)$ time algorithm, this messes up array.

If we have the additional constraint that the array is read-only, then we can make a copy and deal with the copy, or use an additional data-structure like an order statistics balanced binary tree to do the counting, both of which use $\Theta(n)$ space.

The current question is to try and better the space, while not affecting the run time. i.e.

Is there an $O(n\log n)$ time algorithm to count the number of inversion pairs, which works on a read-only array and uses sub-linear (i.e. $o(n)$) space?

Assume a uniform cost RAM model and that the elements take $O(1)$ space and comparison between them is $O(1)$.

A reference will do, but an explanation will be better :-)

I tried searching the web, but could not find any positive/negative answer for this. I suppose this is just a curiosity.

• Chan and Pătraşcu give an $o(n \log n)$ time algorithm, but as far as I can tell from skimming the paper, they need $\Omega(n)$ space. – Raphael Aug 15 '12 at 21:18
• Furthermore, Ajtai et al. prove that any (exact) $O(n)$ time streaming algorithm needs $\Omega(n)$ space. There seem to be approximations fitting your criteria, though. – Raphael Aug 15 '12 at 21:25
• @Raphael: Thanks! If no answer is forthcoming, your comment would be the best answer so far. – Aryabhata Aug 16 '12 at 2:35
• BTW I am a little confused about that Ajtai et al lower bound. Theorem 8 says "any algorithm", but the lower bound to me seems to be against single pass exact streaming algorithms, a very restricted model – Sasho Nikolov Aug 16 '12 at 4:23
• @SashoNikolov: I think they globally set their model to streaming algorithms, so "any" would be restricted to those. I hope that my corollary -- any exact $O(n)$ time algorithm -- is correct, that is that any linear-time algorithm can be expressed as a streaming algorithm with constantly many passes. We'll see. – Raphael Aug 16 '12 at 8:26

Chan and Pătraşcu give an $o(n\log n)$ time algorithm, but as far as I can tell from skimming the paper, they need $\Omega(n)$ space. Furthermore, Ajtai et al. prove that any (exact) $O(n)$ time streaming algorithm needs $\Omega(n)$ space. There seem to be approximations fitting your criteria, though.