I've finished optimizing and testing Spreadsort (integer_sort/float_sort/string_sort), a hybrid radix-based/comparison-based algorithm. It is now available from: http://sourceforge.net/projects/spreadsort I have tested it using an (included) automated test script on Mac OSX and Cygwin with a range of different distributions of random data on 20MB data sets. It is roughly twice as fast as std::sort on average across all three data types and many distributions, with the main exception of a 28X average performance improvement for float_sort on Cygwin. Average runtime seems to be proportional to roughly theta(n*square_root(log(n))); worst-case is more complicated but better than O(nlog(n)), due to the radix-based portion. Test it and see for yourself how it performs on your system. At this point I'm looking for suggestions on formatting it to submit as a Boost.Algorithm.Sorting namespace. I would appreciate comments that aid that process. I am also interested in knowing whether people would like a parallel_sort integrated in Boost.Algorithm.Sorting with Spreadsort.