Stable comparison sort with $O(1)$ auxiliary memory and $O(n \log n)$ average running time
There is a sort algorithm with $O(1)$ auxiliary words and achieving $O(n\log n)$ worst-case run time, where $n$ is the length of the input array.
http://www.springerlink.com/content/d7348168624070v7/

I don't think that the question seeks an algorithm with $O(1)$ auxiliary bits, because such algorithm must be tricky.  I mean, if we cannot use even $O(\log n)$ bits, then we cannot use a simple for-loop (for(i=0, i &lt; n, i++) {...} ) in the algorithm without introducing variable i (which require additional $O(\log n)$ bits).