on Sun Jul 06 2008, "Steven Ross" <spreadsort-AT-gmail.com> wrote:
FWIW, the requirements of std::sort are satisfied by quicksort, an algorithm that works on bidirectional iterators only (it just depends on partition and swap), and if you allow it to be adaptive (i.e. use temporary storage) it can work on forward iterators (see std::stable_partition) -- although the latter may not be any faster than copying into a vector, sorting that, and copying back.
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?
and SGI's STL implementation uses Introsort, which uses a random access iterator.
Yes, I know.
The first version of Spreadsort I wrote in 2001 allocated separate memory for each bin, and with a linked-list approach instead each sorting operation could be done in a single pass (as opposed to the three passes used in the version I'm turning into integer_sort), though without finding the maximum 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 misses, 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 ;-)
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. -- Dave Abrahams BoostPro Computing http://www.boostpro.com