I mentioned that in the first comment. Fast in-place stable sorts usually have a step where they must freely rearrange some things (blocks, medians, etc.) and r

I mentioned that in the first comment. Fast in-place stable sorts usually have a step where they must freely rearrange some things (blocks, medians, etc.) and remember their original order, to preserve stability in case some of them were equal. It seems like no one can squeeze the number of these things below sqrt(n). If you have sqrt(n) extra space, you can store a permutation there. If you don't, you use part of the array itself as temporary bit storage, by changing the relative positions of elements. That's where the complexity comes from.