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

[ixid]

On Monday, 7 November 2011 at 20:33:19 UTC, 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/

This sounds good, you should also contact the forum user Philippe 
Sigaud to see if he's made any progress with his templated 
sorting network idea for small number of items and combine the 
two to provide very effective sorting.