Re: [boost] [library submission] smoothsort

Subject: Re: [boost] [library submission] smoothsort
From: Christopher Jefferson (chris_at_[hidden])
Date: 2008-12-14 10:05:40

I would certainly be interested in such a library.

Have you benchmarked it against std::sort in any compilers?

Chris

On 14 Dec 2008, at 14:18, Edouard A. 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.
>
>
>
> 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). 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.
>
>
>
> Kind regards.
>
>
>
> -- 
>
>
>
> Edouard Alligand
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost