Regarding implementing a stable sort for Phobos

[deadalnix]

Le 13/03/2012 17:38, Xinok a écrit :
> On Tuesday, 13 March 2012 at 16:04:55 UTC, deadalnix wrote:
>> Le 13/03/2012 16:08, Xinok a écrit :
>>> On Tuesday, 13 March 2012 at 09:32:49 UTC, deadalnix wrote:
>>>> Le 13/03/2012 10:19, Xinok a écrit :
>>>>> Would you mind sharing your smoothsort? I haven't implemented one
>>>>> myself
>>>>> and I'd love to test it out.
>>>>
>>>> It is on github :
>>>> https://github.com/deadalnix/Dsort/blob/master/sort/smooth.d
>>>
>>> Thanks. I found a couple cases where it performs better, but overall,
>>> the overhead of the algorithm seems to be too much and most other
>>> algorithms performed better.
>>
>> smooth sort is intended to be used on semi sorted data (like
>> transparent polygons on a 3D scene). Ideal to keep some data sorted.
>>
>> It also have a guarantee to run in O(n*log(n)). But qsort variation
>> (like we have in phobos) is faster in the general case.
>
> It only performs well if there aren't many elements to move around. For
> example, I took a sorted list with 1 million elements, and appended 64
> random elements. Smoothsort was the second slowest, only marginally
> beating heap sort. My natural merge sort was 27x faster.

Yes, that being said, my implementation use multiple swap where move 
would have been more appropriate, and don't implement some improvements.

Merge sort is also known to be very fast (it is default is some 
langauges) but trigger memory allocation, something that some cannot afford.

Definitively, this is something we should have in phobos.