Does there exist a stable comparison sort using $O(1)$ auxiliary memory and achieving $O(n \log n)$ average run time?
Context: There are comparison sorts with any two of those three desirable characteristics (see this list). Is there a reason why the three cannot be achieved simultaneously? [Edit: I added the algorithm from the accepted answer to the list on Wikipedia, obviously it wasn't there when I asked the question.]
springerlink.com
in a comment above is broken, but the article can be found at doi:10.1007/s00224-006-1311-1. $\endgroup$