Adam,
And finally, every review should attempt to answer this question:
- Do you think the library should be accepted as a Boost library?
No. This library has potential, but is too specific for a what I would expect from a Sort library. I believe the only way to get something like this into boost is to provide Spreadsort as one among many algorithms. This will also allow benchmarks and comparisons to be performed among the various algorithms directly, as well as provide a foundation and building blocks for more advanced usage.
As an aside, I am very interested in Spreadsort! I would like to see it available, definitely. But certainly there must be situations where other algorithms are a better fit.
I think LSD radix sort is a valid alternative because it's stable, and possibly a stable hybrid radix sort. Other possibilities are using sorting networks instead of insertionsort for really small lists, and an algorithm optimized for mostly sorted lists, but each of these has decreasing marginal benefit. The idea with this library is that you don't need to worry about the algorithm, it uses radix and/or comparison based sorting as best suits your problem. The Perl script tune.pl provides a basic benchmarking and parameter tuning setup. Do you have a specific use case you'd like to use another algorithm for?