Patch: Improve std::sort performance (particularly on reverse-ordered lists)

[David Kastrup]

Christopher Jefferson <chris@bubblescope.net> writes:

> This is just posting a patch from bugzilla, so it gets a wider
> audience. The patch seems to be performing well.

Apropos the headline "particularly on reverse-ordered lists": while it
is probably not really talking about _lists_, it's worth mentioning that
I posted rather well-performing (stable, close to minimum comparisons,
memory locality pretty good for lists, considerably better performance
than current list sort, no degenerate worst case behavior) list-sorting
code to this list several months ago, answered a few questions and never
got any conclusive followups or suggestions apart from an acknowledgment
that my numbers seemed correct.

So while it would appear from your discussion of quicksort that you are
more concerned with arrays rather than lists (correct me if I'm wrong),
it might be worth a look anyway.

Here's the original mail in the archive
<URL:http://gcc.gnu.org/ml/libstdc++/2013-07/msg00010.html>.

-- 
David Kastrup