This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: Possible improvement to std::list::sort
- From: David Kastrup <dak at gnu dot org>
- To: libstdc++ at gcc dot gnu dot org
- Date: Wed, 08 Oct 2014 05:48:00 +0200
- Subject: Re: Possible improvement to std::list::sort
- Authentication-results: sourceware.org; auth=none
- References: <543474B2 dot 5000401 at gmail dot com>
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