finding the parity of a permutation in little space 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.
 A: 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.
A: I can suggest an algorithm with $\tilde{O}(\sqrt{n})$ space and $\tilde{O}(n \sqrt{n})$ time complexities. One can divide the array into $\sqrt{n}$ chunks of similar size and compute number of inversions in each. After that we compute for each chunk how much inversions elements left to the chunk make with the chunk.
The algorithm can be modified to use $\tilde{O}(s)$ space and $\tilde{O}(\frac{n^2}{s})$. 
UPD: Smart people suggest paper http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.2256
Parity of permutation can be expressed in terms of parity of numbers of its cycles (n - c mod 2). The paper provides at least two algorithms for computing them. The basic idea is to determine the unique cycle leader for each cycle. For example, the minimal element on a cycle can be such a leader. One can easily obtain an algorithm, which uses $O(n^2)$ time and $O(\log n)$ memory, for computing number of cycles.
One of the algorithms picks 5-wise independent hash-function and chooses the minimal element by this function as a leader. Traverse each cycle and if you find an element with smaller hash-value than initial, stop traversing. Otherwise, traverse cycle up to closing, and then increment counter of cycles.
The algorithm works in $O(n \log n)$ time and $O(\log n)$ memory.
The authors also provide a complicated deterministic algorithm with $O(n \log n)$ time and $O(\log^2 n)$ memory.
A: It strikes me that you are going to need to remember either the index i or the value pi(i), so barring "magic memory", you are going to need log n bits as a strict minimum.  For small n, you may as well use the n bits and a straightforward algorithm.
If you are able to modify the given array, there is at least one O(n) algorithm which allows you to undo the permutation in an most (n-1) swaps, using Clog n bits for some small C, perhaps C<3.
There are a couple of bit manipulation ideas that you might find useful if you are really saving space.  I am not sure how to incorporate them into an O(n) time algorithm, but someone else here on MathOverflow might.
The first works if n/d is small, where n>d>0 and n+d is a power of 2. You can then relabel d numbers to be larger than n. However, you need log n bits to remember n, and you have to be very clever or very stupid to make use of the relabeling.
The other idea is a space-saving method for doubly-linked lists. It involves some function using the current, next, and previous locations and xoring some of them together, so when you traverse the list in some direction, you use that information and xor to decode the next location.  I apologize for not recalling all the details.  
These are worth doing only if n is large, or if the circuit you are building is quite small.
Gerhard "Ask Me About System Design" Paseman, 2011.08.11
