Re: [boost] [library submission] smoothsort

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;
                                ln.up<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
files.

-- 
Edouard