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]>
> 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,
> string versions, with functor version for flexibility. It's roughly
> 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
> 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
> 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk