pdqsort VS ips4o

I found that this exists: https://github.com/orlp/pdqsort

Their sort_unstable algorithm is based on this pattern-defeating quicksort.

Closely related is pattern defeating quicksort ( https://github.com/orlp/pdqsort ), which adapts quicksort to take advantage of sorted runs. I've adapted a few quicksorts to pdqsort and seen good speedups (as people were often sorting partially sorted data)

Basically: Timsort is to mergesort as pdqsort is to quicksort

I was thinking of optimal C++ over native types. I just spoke up because if your intuition of quicksort is that 50k elements should take 20ms you’re drastically underestimating computer performance. They’re crazy fast and optimized sorting algorithms are downright scary.

Just for fun, I added pdqsort to the benchmark:

https://github.com/orlp/pdqsort

Here are some of the results on an Ivy Bridge hackintosh:

      size, qsort, inline, sort, stable_sort, pdqsort, radix7

sort_unstable is a pattern-defeating quicksort (https://github.com/orlp/pdqsort) added with RFC#1884 (https://github.com/rust-lang/rfcs/pull/1884).

A while ago I was tinkering with Quicksort and avoiding branch mispredictions.

https://easylang.online/blog/qsort_c.html

My implementation is pretty fast. At a size of 40 or 50, I switch to Insertion sort, and there the branchless bubblesort is significantly slower (I just tried it).

But I have to admit defeat to this SampleSort:

https://github.com/SaschaWitt/ips4o

For sorting, not really. The big development in compute power is parallelism. ips4o facto (https://github.com/SaschaWitt/ips4o), if you want to sort large vectors really fast it makes more sense to sort in-place and in parallel. Parallel in-place radix sort is also choice, but way less flexible than comparison sort.