Re: [boost] [library submission] smoothsort

Subject: Re: [boost] [library submission] smoothsort
From: Steven Ross (spreadsort_at_[hidden])
Date: 2008-12-14 19:46:25

On Sun, Dec 14, 2008 at 2:25 PM, Edouard A. <edouard_at_[hidden]> 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?