Re: [boost] [library submission] smoothsort

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
> hard. 

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
> std::list. 

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