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
> of a library, but where to place it? And I'm sure we could figure out a
> 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?
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk