On Sun, 14 Dec 2008 16:46:25 -0800, "Steven Ross" <spreadsort@gmail.com> wrote:
On Sun, Dec 14, 2008 at 2:25 PM, Edouard A. <edouard@fausse.info> wrote:
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?
That sounds like a good idea, if I understood correctly what you propose is to start building up a Boost.Sorting library? Even more good news, I woke with a lot of ideas to improve my existing implementation, this is related to the way leonardo numbers are computed, the current way of doing is clearly suboptimal. -- EA