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, and SGI's STL implementation uses Introsort, which uses a random access iterator. 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. Do you have a genuine desire for a real application to see a bidirectional (or unidirectional) iterator version of a hybrid sort? Spreadsort isn't much slower on a linked list than on an array, so it should do much better than Quicksort. I normally think of sorting linked lists as a rare niche application. In my own work I avoid linked lists because there is a better standard data structure for every problem I've run into.
and should be just as flexible. I will see if using some generic algorithms for iterators improves the performance a little; I'm seeing a noticeable speed penalty with iterators instead of pointers. I get the same performance as the old code when I pass in pointers as the iterators, but a roughly 15% increase in runtime when I use .begin() and .end().
What compiler are you testing? VC++ uses checked iterators by default, which slows everything down terribly. You might try putting -D_SECURE_SCL=0 in your command line. See
http://einaros.blogspot.com/2007/02/iteration-techniques-put-on-benchmark.ht...
I'm using g++ on an OSX laptop with a G4 processor (slow and old, in other words). I tried your suggested command line option and it made no visible difference, but thanks for the suggestion. If I sort using &(vec[0]), &(vec[0])+vec.size(), it still runs 15% faster than with vec.begin(), vec.end(). Steve