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

[Xinok]

Recently, I've been working on my sorting algorithm, doing what I can 
before I implemented it into std.algorithm. Recently, I've found myself 
referring to Timsort for ways to optimize my algorithm, but that made me 
think, why not use Timsort instead? It was originally designed for 
Python, but it was apparently good enough for Java to adopt it as well.

I think Phobos would benefit most from a good implementation of Timsort, 
perhaps enough to even ditch the unstable sort which I've found has some 
bad test cases (try sorting swapRanges(arr[0..$/2], arr[$/2..$])). My 
algorithm is very similar to Timsort, but Timsort is more highly tuned, 
so it would probably beat my algorithm in most cases. In a few 
benchmarks I've seen, Timsort even beats quicksort.

The only downside is that Timsort may require up to O(n/2) additional 
space, and if it fails to allocate enough memory, it simply fails to 
sort the list. That's the benefit of my algorithm, it allocates 
O(n/1024) additional space by default and can reduce it further if 
needed. However, the "range swap" that my algorithm uses could easily be 
added to Timsort as well, so we could have the best of both worlds: The 
speed of Timsort with the low memory requirement of my algorithm.

This is my proposal: Replace the stable (and unstable?) sort in Phobos 
with Timsort, including the additional range swap step.

An explanation of Timsort can be found here:
http://svn.python.org/projects/python/trunk/Objects/listsort.txt

My algorithm can be found here (see the blog for more details):
https://sourceforge.net/projects/xinoksort/