Re: [boost] Proposed templated integer_sort

From: David Abrahams (dave_at_[hidden])
Date: 2008-07-06 18:21:22

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