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.
