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

[dsimcha]

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.

On 11/7/2011 3:32 PM, Xinok wrote:
> 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/