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 acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk