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)$ space (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)$ space?