# Optimal comparison-based stable sorting in constant space

For a comparison based sorting algorithm, it is desirable to:

1. Be stable
2. Run in $O(n\ \log n)$
3. Operate in $O(1)$ space

I can find algorithms that satisfy any two of these but I can't find any that satisfy all three. Does it exist? Is it proven not to exist?

• I think that the algorithm uses $O(1)$ pointers, but has a recursive call stack that is logarithmic in the size of the list. Am I mistaken? Apr 11 '12 at 11:54