A quasi-answer: quick sort will determine the parity in expected $O(n log n)$ time and $O(1)$ space.

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.