Boost logo

Boost :

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." <> 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

Boost list run by bdawes at, gregod at, cpdaniel at, john at