pdqsort VS quadsort

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).

https://github.com/scandum/quadsort/blob/f171a0b26cf6bd6f6dc...

As you can see, quadsort 1.1.4.1 used 2 instead of 4 writes in the bi-directional parity merges. This was in June 2021, and would have compiled as branchless with clang, but as branched with gcc.

When I added a compile time check to use ternary operations for clang I was not adapting your work. I was well aware that clang compiled ternary operations as branchless, but I wasn't aware that rust did as well. I added the compile time check to use ternary operations for a fair performance comparison against glidesort.

https://raw.githubusercontent.com/scandum/fluxsort/main/imag...

As for ipnsort's small sort, it is very similar to quadsort's small sort, which uses stable sorting networks, instead of unstable sorting networks. From my perspective it's not exactly novel. I didn't go for unstable sorting networks in crumsort to increase code reuse, and to not reduce adaptivity.

In the code it looks like the seed to the benchmark can be provided as the 4th command line argument: https://github.com/scandum/quadsort/blob/master/src/bench.c#...

If you look at sorting for example, it's been proven that you can't do a comparison-based sort faster than O(n logn). You may then think that we've already found the fastest possible sorting algorithms since Quicksort and Mergesort are already O(n logn). However, new sorting algorithms keep being invented, for example Quadsort. They're all still O(n logn), but they do offer a considerable speed improvement over more traditional algorithms