Re: [boost] [library submission] smoothsort

Subject: Re: [boost] [library submission] smoothsort
From: Edouard A. (edouard_at_[hidden])
Date: 2008-12-15 03:40:25

On Sun, 14 Dec 2008 16:46:25 -0800, "Steven Ross" <spreadsort_at_[hidden]>
wrote:
> On Sun, Dec 14, 2008 at 2:25 PM, Edouard A. <edouard_at_[hidden]> 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