A Benchmark for Phobos Sort Algorithm

[Sean Kelly]

Nick Voronin Wrote:

> On Thu, 16 Dec 2010 04:52:53 +0300, Craig Black <craigblack2 at cox.net>  
> wrote:
> 
> 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.

A tweaked version of the Tango sort routine is slower for random data but roughly 25% faster for ordered data.  The straightforward quicksort is about 30 times slower though.  All in all, the Phobos sort routine seems to do quite well.  I'd like to see a test with other types of contrived worst-case data though.