This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Possible improvement to std::list::sort


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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]