Benchmark results

[Azmisov]

My use case was 100k items with lots of duplicates. I compared my own Floyd-Rivest implementation, your code, and nth_element. For small lists, nth_element was the fastest, with Floyd-Rivest and quickselect-adaptive both about twice as slow. For large lists, Floyd-Rivest was the fastest, about 30% faster than nth_element. Quickselet-adaptive was actually the slowest, being 20% slower than nth_element.

I guess this isn't necessarily an issue; just information for whoever may be looking for select algorithm implementations.

[terrelln]

This is still a work in progress, with progress currently stalled.

One of the problems I was having when I stopped working on this is handling duplicate elements.
If I remember correctly, benchmarks I ran were about the same or a bit faster than nth_element when there aren't duplicate elements, but that was a while ago.

It looks like Andrei Alexandrescu released his implementation of the algorithm in the D standard library. I'll have to see what tricks he uses.

[Morwenn]

I've got a sorting algorithm that heavily relies on std::nth_element, so I tried to find several implementations of the function to make it as fast as possible. In this process, I benchmarked several implementations, and thought that it was worth sharing the results here since I used yours:

The benchmark involved sorting 1 million integers with different patterns. The sorting algorithm is always the same, only the selection function changes. Here are the selection functions used:

• quick_merge_sort1 -> libstdc++ std::nth_element
• quick_merge_sort2 -> libc++ std::nth_element
• quick_merge_sort3 -> Andrei Alexandrescu's adaptiveQuickselect from this repository
• quick_merge_sort4 -> your implementation of quickselect_adaptive

Everything has been compiled with MinGW-w64 g++7 -O3 -march=native -NDEBUG

As you can see, for that specific use case, your function is the best for some patterns. Not sure what makes the difference, but the results are promising :)

[terrelln]

Thanks @Morwenn! I haven't worked on this in a while, I should pick it back up. I'm happily surprised that it is competitive with Andrei's implementation.

[Morwenn]

No problem :)

I also just tried to ressucitate another selection algorithm I whipped up a while ago, based on pdqsort. Unfortunately, it isn't as good as I thougt it would be. Here is how it performs compared to the other ones (pdqselect is the 5th one):

Considering how fast pdqsort is, I thought pdqselect would be faster than the alternatives. I may have missed something when adapting the algorithm. If you're interested, you can look at pdqsort's partitioning scheme: it uses branchless partitions when possible, so you might find some ideas in it to improve adaptive_quickselect.

The background story for the QuickMergeSort algorithm is that I was trying to find an in-place O(n log n) comparison sorting algorithm that performed better than heapsort, and didn't fallback to heapsort like all quicksrt derivatives do. With libc++'s std::nth_element, QuickMergeSort is decent enough, but a better selection function may make it more competitive :)