From: Steven Ross (spreadsort_at_[hidden])
Date: 2008-07-06 18:47:26
> > That may be true, but Introsort is significantly faster both on
> > average and worst-case than Quicksort,
> As I have always understood it (and as Musser's paper describes it),
> introsort *is* Quicksort until its behavior starts to stray from the
> average case, when it switches to heapsort as a fallback. How could it
> possibly have better average case complexity than Quicksort?
1) Mean performance across all testcases does not mean just Quicksort's
best-case. Heapsort is a good general algorithm, and improves the average
performance even if it doesn't change much on random data.
2) Introsort also uses insertion_sort, which is really fast on small data
sets. I used to use Quicksort for recursive calls from Spreadsort, then
found that for sizes up to 16 it was much better to use insertion_sort. So
for the final sorting of very small data sets after it's finished cutting
them up, introsort is faster.
3) In benchmark testing I find introsort to be about 3X as fast as the qsort
library call. That should be the strongest argument of all.
> > The first version of Spreadsort I wrote in 2001 allocated separate memory
> > for each bin, and with a linked-list approach instead each sorting
> > could be done in a single pass (as opposed to the three passes used in
> > version I'm turning into integer_sort), though without finding the
> > and minimum values. That would make more sense to use with a linked-list
> > data set. It's not complicated to implement, but my testing shows that
> > iterating through linked lists is slow because they often have cache
> > and besides, binary search only makes sense in a data structure that
> > supports random access.
> You might consider why the STL provides binary search for forward
> iterators, then ;-)
That might save a little iteration over a search over every element, but
wouldn't it still be O(n)?
I'd think it's there just because it's possible, not because it has much
use. I have no problem with providing general capabilities just because
> > Do you have a genuine desire for a real application to see a
> > bidirectional (or unidirectional) iterator version of a hybrid sort?
> I'm just generally interested in algorithms.
It would be at least a few hours of development plus testing to make sure it
isn't broken. I'd be happy to tell you how to do it if you wish, but
without a need, I don't see why I should bother. I have many things to do,
and little time.