Worst case $O(n \ln n)$ in place stable sort?
You can write an in-place, stable mergesort. See this for details. In the author's own words:


  A beautiful in place - merge algorithm. Test it on inverted arrays to understand how rotations work. Fastest known in place stable sort. No risk of exploding a stack. Cost: a relatively high number of moves. Stack can still be expensive too. This is a merge sort with a smart in place merge that 'rotates' the sub arrays.  This code is litteraly copied from the C++ stl library and translated in Java. 


I won't copy the code here, but you can find it at the link or by checking the C++ STL. Please let me know if you would like me to try to provide a more detailed description of what's going on here.