On Sun, Dec 14, 2008 at 2:25 PM, Edouard A. <edouard@fausse.info> wrote:
I was thinking the same, by itself smoothsort would not justify the creation of a library, but where to place it? And I'm sure we could figure out a nice catalog of algorithms to implement.
I have a Spreadsort-based hybrid radix-based/comparison-based library I'm preparing to submit as a proposed Boost library (currently I'm regression testing a final version). I've finished adding integer, floating-point, and string versions, with functor version for flexibility. It's roughly twice as fast as std::sort across a wide range of (random) distributions. It's even faster (more than 2X) on already-sorted data relative to std::sort. I propose this: 1) Combine your unmodified smoothsort implementation with my sorting library, which I consider a logical combination. 2) I can implement versions of integer_sort, float_sort, and string_sort that use smoothsort for their comparison-based sorting approach (currently it uses std::sort), which would provide an algorithm that (ideally) is no slower than std::sort on the vast majority of data sets, and is much faster on already-sorted data. I could also convert the versions which use smoothsort to use std::advance to support non-random-access iterators. Does that interest you?