There's an issue here that I <i>really</i> don't understand: why is this never used?<p>For example, the original C++ STL generally did a heck of a good job at exposing an interface to the 1997 state of the art in general-purpose algorithms. So, the spec for std::stable_sort was aimed at Mergesort: O(n log n) comparisons and O(n) additional space due to the space required by the Stable Merge. <i>HOWEVER</i>, if limited space is available, then it is allowed to use O(n log n log n) comparisons, since a slower in-place algorithm is used. [1]<p>Why? With the algorithm from this article, we can do an O(n log n) in-place Mergesort. I imagine it's not as fast as the standard algorithm that requires O(n) additional space -- although the abstract of this article does call the in-place merge algorithm "reasonably competitive". But it certainly sounds like it would be a better fall-back option.<p>Similarly, lots of languages have moved toward some version of Mergesort for their standard sorting algorithm: Perl, Python ("Timsort" is a Mergesort variant). Even some versions of the "C" Standard Library's qsort are implemented with Mergesort these days. I never hear about any of these being in-place. But the work in this article isn't exactly a secret.<p>So: I don't get it.<p>[1] EDIT: I checked the C++11 spec. It is the same. std::stable_sort does O(n log n) comparisons if sufficient memory is available, and O(n log n log n) if not.