[Bug libstdc++/58437] [4.7/4.8/4.9 Regression] Sorting value in reverse order is much slower compare to gcc44

[chris at bubblescope dot net]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58437

--- Comment #16 from Chris Jefferson <chris at bubblescope dot net> ---
Indeed, if std::sort had never used lower-level partitioning to get the pivot
in the correct location, we would never have had this problem in the first
place!

This is not too serious a problem performance-wise (as the pivot ends up in the
right place fairly quickly), but it would certainly be better to do that in
future. Unfortunately doing this requires changing quite a few functions, to
make all code which uses partition skip over the pivot value.

I would suggest my current patch (which is simpler than it looks from the diff)
for previous versions, then investigate pivot. In general I would like to
modernise the sort to match more modern thoughts on sorting such as making use
of partly sorted data (which would include reverse-ordered). The only problem
there is satisfying all the requirements of std::sort).

(detail: -p doesn't help, you just get things like " -110,16 +112,18 @@
_GLIBCXX_BEGIN_NAMESPACE_VERSION". Neither -u 10, -x -u 10 or -x "-u 10" seem
to work, I just get errors. If you can give me the exact svn diff command to
run to get nicer output, I am happy to do so).