A Benchmark for Phobos Sort Algorithm

[Nick Voronin]

On Thu, 16 Dec 2010 04:52:53 +0300, Craig Black <craigblack2 at cox.net>  
wrote:

> On my computer, the custom sort algorithm performs almost 40 percent  
> better than the Phobos one.  I provided this in case anyone wanted to  
> improve the phobos algorithm.  I only benchmarked this with DMD.  I  
> would be curious to know how it performs with GDC.

Benchmarks! Love them. They will show whatever you want them to. For  
example I see that customSort is of different complexity and much slower  
than phobos' sort. =)

> void quickSort(A, alias L)(A a, int p, int r)
> {
>   if (p >= r) return;
>   if(p + 7 > r) return insertionSort!(A, L)(a, p, r);
>   auto x = a[r];

And here is why. Quicksort is quite famous for being O(n^2) worst case  
(for sorted data). Your straightforward, simple  (and less generic, I must  
say) implementation shines for random data, but performs terribly for  
ordered data. Phobos' sort isn't really plain quicksort so it is slower  
for random data (yet still of the same complexity as your code best case),  
but it is pretty fast for ordered data.

I wonder though, what exactly makes std.algorithm.sort twice slower for  
random data... overhead of ranges? more complex logic/more code?

-- 
Using Opera's revolutionary email client: http://www.opera.com/mail/