Re: [boost] [library submission] smoothsort

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:

> Hello,
>
>  
>
> 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
> library.

Absolutely, IMO.  I think we might need a general algorithms library to
put it in.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com