Suppose we have a permutation $\pi$ on $1,2,\ldots,n$ and want to determine the parity (odd or even) of $\pi$.
The standard method is find the cycles of $\pi$ and recall that the parity of $\pi$ equals the parity of the number of cycles of even length. However this seems to require $\Theta(n)$ bits of additional memory to carry out in linear time. (As you trace each cycle, you need to mark its elements so that you can avoid tracing the same cycle again.)
Alternatively, using only $O(\log n)$ bits (a few integer indexes), the inversions can be counted. This takes $\Theta(n^2)$ time, using the naive algorithm.
So my question: can the parity be determined in $O(n)$ time and $O(\log n)$ bits?
I have in mind that the input is a read-only array $p$ where $p[i]=\pi(i)$. An interesting variation is to allow the array to be modified. But you can't assume each array element has more than enough bits to hold the integer $n-1$ (not $n$, because I want only the values $1,\ldots,n$ to be representable; you don't get an additional value to use as a marker) or else you need to count the extra bits as working space and linear time becomes easy.
Best Answer
A quasi-answer: quick sort will determine the parity in expected $O(n log n)$ time and $O(1)$ space.
EDIT As pointed out, quick sort actually uses up some stack, so uses $O(\log^2 n)$ space. Heapsort has the same time complexity, and $O(1)$ space complexity, and there is, apparently, an in-place merge sort with the same properties.