Re: [boost] [library submission] smoothsort

Subject: Re: [boost] [library submission] smoothsort
From: Edouard A. (edouard_at_[hidden])
Date: 2008-12-14 12:08:17

I have done only very few tests. For the moment the theory doesn't seem to
pay off. Although the complexity should be close to O(N) for sorted input,
std::sort performs incredibly well on such sorted input (MS' implementation
is an introspective sort).

To use a technical term, std::sort is currently spanking my smoothsort very
hard. 

This will need more tests, and again, my implementation is not optimized.
For example I have kept iterator's arithmetic generic so that it may work on
std::list. A hint that I can do much better is that even std::make_heap,
std::sort_heap outperforms my current implementation.

Compiler : Visual Studio 2008, x64 platform, all optimizations known to me
turned on. 
Processor : Intel Q6600.

-- 
Edouard
> -----Original Message-----
> From: boost-bounces_at_[hidden] [mailto:boost-
> bounces_at_[hidden]] On Behalf Of Christopher Jefferson
> Sent: dimanche 14 décembre 2008 16:06
> To: boost_at_[hidden]
> Subject: Re: [boost] [library submission] smoothsort
> 
> 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
> 
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost