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
