Sorting algorithm

[Xinok]

On 10/7/2011 2:20 PM, Andrei Alexandrescu wrote:
> On 10/7/11 12:23 PM, Xinok wrote:
>>>> http://www.neowin.net/forum/blog/422/entry-3737-sort-algorithm-complete/
>>>>
>>>
>>> This is interesting. What do the numbers in the benchmark represent?
>>>
>>> Andrei
>>
>> I'll just post the code I used for benchmarking. Simply put, smaller
>> numbers are faster.
> [snip]
>
> Thanks. It would be great if you wanted to contribute your stable sort
> to Phobos via a pull request.
>
> Also, which version of D are you using? I'm seeing that
> std.algorithm.sort (introSort) performs quite badly; for example, it's
> twice as slow on shuffled data against quickSort, and it also deals
> badly with already sorted data. Generally it does much worse than the
> quickSort baseline. Wonder why.
>
>
> Andrei

I'm not familiar with the process. What all would I need to do to 
contribute my sort to Phobos?

On another note, my sort is most efficient on random access ranges. A 
simple merge sort would be more practical for other data structures like 
linked lists.

I used DMD 2.051 for those benchmarks, so I did new benchmarks using DMD 
2.055. Unstable sort saw a big improvement, but stable sort still did 
poorly. I find it unusual since I thought stable sort was supposed to 
use merge sort.

xinokSort:       7564654
shellSort:       8843484
quickSort:       6005074
mergeSort:       6625306
radixSort:       2837697
phobos Unstable: 5559726
phobos Stable:   113924852