I am having trouble finding good resources that give a worst case $O(n \ln n)$ in place stable sorting algorithm. Does anyone know of any good resources?
Just a reminder, in place means it uses the array passed in and the sorting algorithm is only allowed to use constant extra space. Stable means that elements with the same key appear in the same order in the sorted array as they did in the original.
For example, naive merge sort is worst case $O(n \ln n)$ and stable but uses $O(n)$ extra space. Standard quicksort can be made stable, is in place but is worst case $O(n^2)$. Heapsort is in place, worst case $O(n \ln n)$ but isn't stable. Wikipedia has a nice chart of which sorting algorithms have which drawbacks. Notice that there is no sorting algorithm that they list that has all three conditions of stability, worst case $O(n \ln n)$ and being in place.
I have found a paper called "Practical in-place mergesort" by Katajainen, Pasanen and Teuhola, which claims to have a worst case $O(n \ln n)$ in place stable mergesort variant. If I understand their results correctly, they use (bottom-up?) mergesort recursively on the first $\frac{1}{4}$ of the array and the latter $\frac{1}{2}$ of the array and use the second $\frac{1}{4}$ as scratch space to do the merge. I'm still reading through this so any more information on whether I'm interpreting their results correctly is appreciated.
I would also be very interested in a worst case $O(n \ln n)$ in place stable quicksort. From what I understand, modifying quicksort to be worst case $O(n \ln n)$ requires selecting a proper pivot which would destroy the stability that it would otherwise normally enjoy.
This is purely of theoretical interest and I have no practical application. I would just like to know the algorithm that has all three of these features.