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