Boost logo

Boost :

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

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