Nick Voronin Wrote: > On Thu, 16 Dec 2010 04:52:53 +0300, Craig Black <[email protected]> > 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.
