quadsort VS piposort

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

Hang on, you can't just quote MB/s numbers for an O(n log(n)) sort. What length were these tests run at?

The code size might not end up quite as good, but a branchless merge sort is a contender for a fast and lightweight merge. Just published, tiny-sort-rs[0] cites 632 bytes and looks like ~350MB/s at 1e4 elements on Zen 3. In my tests, my own pisort[1] benches a little over twice as fast as LongSort, but it uses sorting networks as the base case so it's like 5KB. It's roughly based on piposort[2] which has more complicated recursion but a simpler base case.

400 MB/s seems a bit slow for a radix sort on that hardware: I'm hitting those numbers on my i5-6200U, which has less than half the clock rate, with my own radix sort. Recommend checking ska_sort_copy from [3] as it has about the same performance.

[0] https://github.com/Voultapher/tiny-sort-rs

[1] https://github.com/mlochbaum/SingeliSort/blob/master/src/mer...

[2] https://github.com/scandum/piposort

[3] https://github.com/skarupke/ska_sort

Quadsort's author here.

This is the first time I've heard quadsort being called esoteric. It isn't much more complex than Timsort. It is however challenging to port ~1000 lines of code that can be tedious to debug. If you make one simple error/typo you could be stuck for hours in debugging hell.

Hence I recently published piposort, which is ~150 lines and pretty basic, while still offering excellent performance. Not as good as quadsort, but it could make for a stepping stone in a porting effort.

https://github.com/scandum/piposort