Should Phobos use Timsort instead? (with a small tweak)

[Xinok]

On 11/7/2011 7:47 PM, dsimcha wrote:
> Phobos definitely needs a decent stable sort. I had been meaning to
> contribute a very highly tuned merge sort that I use for some
> statistical calculations after allocators get into Phobos. Timsort would
> make a good additional option. However, I **strongly** recommend against
> **replacing** a sort that does not require O(n) extra space with one
> that does.
>

Take a look at the graphic here:
http://cl.ly/3L1o111u1M232q061o2N

That's the extra step that I propose adding to Timsort, if it were 
implemented in Phobos. By doing a single range swap, you can reduce the 
space requirement from O(n/2) to O(n/4). My algorithm utilizes it so 
that only O(n/1024) additional space is required.

Timsort would still use up to O(n/2) space, but if it failed to allocate 
enough memory, it could resort to the range swap instead.

I'll leave it up to the community to decide what's best. But if the 
stable sort proves to be faster, has a worst case of O(n log n), and can 
succeed despite failing to allocate additional space, what purpose is 
there in keeping the unstable sort?