Subject: Re: [boost] [library submission] smoothsort
From: David Abrahams (dave_at_[hidden])
Date: 2008-12-14 14:21:09
on Sun Dec 14 2008, "Edouard A." <edouard-AT-fausse.info> wrote:
> I just finished a C++ implementation of the smoothsort algorithm (a
> derivative of the heapsort algorithm by Dijkstra that, in his words, "is of
> order N log N in the worst case, but of order N in the best case, with a
> smooth transition between the two").
> When sorting nearly sorted containers smoothsort achieves excellent
> performances. If you keep sorting the same container, smoothsort may be the
> right algorithm for you.
Awesome. Sounds really useful.
> This implementation works on all sortable containers, with best performances
> on containers supporting random access iterators (in other words,
> smoothsorting a std::list is quite slow).
Why? Is the complexity bound still respected?
> It only requires the "<" operator between two elements and the user
> can supply the function with a binary predicate.
> To my knowledge, there is no equivalent public C++ implementation.
> I was wondering if this was interesting enough to be included in the boost
Absolutely, IMO. I think we might need a general algorithms library to
put it in.
-- Dave Abrahams BoostPro Computing http://www.boostpro.com
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk