Optimal comparison-based stable sorting in constant space
Mergesort satisfies all three requirements (when merging is performed in place).
See Pardo, L.T., "Stable  sorting  and  merging  with  optimal  space  and  time 
bounds", SIAM J. Comput. 6 (1977), 351-372.