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