Regarding implementing a stable sort for Phobos

[Xinok]

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.