Possible improvement to std::list::sort

[David Kastrup]

Ivo Doko <ivo.doko@gmail.com> writes:

> Greetings.
>
> I would like to submit for your consideration an algorithm which, in
> my tests, (mostly) outperforms std::list::sort as currently
> implemented in libstdc++.

Shrug.  I've submitted an algorithm years ago that consistently
outperforms the standard list sort by about 30% on random lists.
Submitting working code will get you nowhere.  If you want to have a
reasonable chance of adoption, you'll need to do all the work yourself
and submit a complete patch.

That being said, I am not a fan of special-casing pre-sorted cases in
generic routines.  If the case occurs often enough in practice, the
application should invest the extra effort of doing the check itself.
Mergesort "special-cases" presorted material already by requiring about
half the number of comparisons than usual.  Of course, that's still
O(n lg n) rather than O(n), but it will also have benefits for partially
sorted lists.


-- 
David Kastrup