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

[Dmitry Olshansky]

12/29/2012 10:49 PM, 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.

[snip]

>> 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.

Let me point out that Phobos has got the Timsort for stable sort in 
2.061. It's precisely the work of Xinok that was integrated after going 
through many rounds of review.

It would great to analyze the extra trick that reduces the amount of 
memory required. If it's proven to be a good speed-size trade-off then 
it could be integrated.

What's would be truly awesome at the moment is highly efficient 
version(s) of sort(s) customized for small ranges. And IRC that's what 
Philippe's sorting networks were good at.

-- 
Dmitry Olshansky