Boost logo

Boost :

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

Good news everyone,

In adding a precomputation for leonardo's numbers I am now consistently
faster than std::sort on (nearly) sorted input (between 10% to 100%).
std::sort is however much better on very random input (where it performs the
best), up to 5 times better.

I also wanted to add an optimization for counting the 0 to the right, but as
surprising as it may sound the naïve

                        while(!(p & 1))
                                p >>= 1;

Is faster than using tables to get the immediate count.

Steven, if this is ok with you I can send you privately the current state of
my implementation. It's less than 10 kb big and consist in only two header


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