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

["glisse at gcc dot gnu.org" <gcc-bugzilla at gcc dot gnu dot org>]

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

--- Comment #14 from Marc Glisse <glisse at gcc dot gnu.org> ---
Hi Chris,

(detail: could you pass -u10, or at least -p, to diff to make the patches
easier to read? It isn't required so you don't have to)

I don't really understand why the pivot is still considered in lower levels of
the recursion at all. So, first we move the pivot to the first position with a
swap:
(pivot, rest...)
Then we partition:
(pivot, small..., big...)
Then we know what the right position is for the pivot (this isn't a stable
sort), so we could put it there with another swap:
(small..., pivot, big...)
And now we can recurse on small and big, and no one needs to look at the pivot
ever again.

>From what I understand of the code, we are instead relying on recursive calls
to eventually sort pivot to the right position, which seems strange to me.