Subject: [boost] [library submission] smoothsort
From: Edouard A. (edouard_at_[hidden])
Date: 2008-12-14 09:18:57
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
To my knowledge, there is no equivalent public C++ implementation.
I was wondering if this was interesting enough to be included in the boost
-- Edouard Alligand
Boost list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk