Re: [boost] [library submission] smoothsort

Subject: Re: [boost] [library submission] smoothsort
From: Edouard A. (edouard_at_[hidden])
Date: 2008-12-14 17:25:08

> > This implementation works on all sortable containers, with best
> performances
> > on containers supporting random access iterators (in other words,
> > smoothsorting a std::list is quite slow).
> 
> Why?  Is the complexity bound still respected?
[Edouard A.] 

You have a lot of std::advance within the algorithm, typically you will do
std::advance(iterator, 25) and the like. Sucks on std::list's iterators. 

> Absolutely, IMO.  I think we might need a general algorithms library to
> put it in.

[Edouard A.] 

I was thinking the same, by itself smoothsort would not justify the creation
of a library, but where to place it? And I'm sure we could figure out a nice
catalog of algorithms to implement. 

>Did you use -D_SECURE_SCL=0
>?
>
>Without that, anything that you do with most iterators is a dog.

\o/ You are my hero I totally forgot about that \o/

Without profiling:

        std::sort running time : 0.098
        std::sort running time (sorted) : 0.024
        Smoothsort running time : 0.367
        Smoothsort running time (sorted) : 0.017
        Press any key to continue . . .

For a 1,000,000 std::vector<long>. And I'm sure it's possible to improve my
implementation as the processing for high entropy input is not very good.

-- 
Edouard