The random-access version of quick_merge_sort runs in O(n²)

[Morwenn]

I ran a quicksort killer like the one described in #178 with the following algorithms from the library - the ones that have a quicksort-like structure:

• quick_sort
• pdq_sort
• quick_merge_sort (both the bidirectional rand random-access iterators versions)

Here are the results:

It is quite easy to see the difference between the O(n log n) and the O(n²) algorithms there. And it clearly shows that the random-access version of quick_merge_sort runs in O(n²). The culprit is the random-access nth_element, which also means that the libc++ implementation of std::nth_element is quadratic.

[Morwenn]

I tried to change the implementation of nth_element for random-access iterators to miniselect's implementation of Andrei Alexandrescu's QuickselectAdaptive selection algorithm. It is very slightly slower than the libc++ algorithm on average, but correctly handles the killer input without going quadratic:

Next step is to steal the miniselect implementation and adapt it as needed.

[Morwenn]

Related: llvm/llvm-project#52747