Subject: Re: [boost] [library submission] smoothsort
From: David Abrahams (dave_at_[hidden])
Date: 2008-12-14 14:23:34
on Sun Dec 14 2008, "Edouard A." <edouard-AT-fausse.info> wrote:
> I have done only very few tests. For the moment the theory doesn't seem to
> pay off. Although the complexity should be close to O(N) for sorted input,
> std::sort performs incredibly well on such sorted input (MS' implementation
> is an introspective sort).
Yeah, SGI was the first implementation I know of to use introsort. By
now I hope they all do.
> To use a technical term, std::sort is currently spanking my smoothsort very
In that case, maybe you'd better prove that smoothsort can outperform
introsort first :-)
> This will need more tests, and again, my implementation is not optimized.
> For example I have kept iterator's arithmetic generic so that it may work on
Using advance() and distance() for that works well, and should be
optimally efficient for random-access iterators. That's what the binary
searches in most std implementations use.
-- Dave Abrahams BoostPro Computing http://www.boostpro.com
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