Our great sponsors
-
glidesort
A Rust implementation of Glidesort, my stable adaptive quicksort/mergesort hybrid sorting algorithm.
-
WorkOS
The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.
> It is my impression that orlp suggests the only relation between glidesort and fluxsort is that they're both stable quicksorts.
So what is the relationship then? I implemented my own branchless partition operator that switches between overwriting / cmov'ing depending on data size (https://github.com/orlp/glidesort/blob/master/src/stable_qui...), my own bidirectional partitioning scheme, my own pivot selection scheme.
As I wrote before "fluxsort's out-of-place stable partitioning. From this I got reminded that not only is out-of-place stable partitioning a thing, it's highly competitive". This is also what I credit on my page: credit to Igor van den Hoven's fluxsort for demonstrating that stable quicksort can be efficient in practice.
And glidesort isn't a quicksort, it is truly a hybrid.
> Similarly, orlp suggests there is no relationship between his branchless merge and quadsort's branchless merge.
I implemented it from scratch (10+ different versions), myself:
https://github.com/orlp/glidesort/blob/master/src/branchless...
You can still see artifacts of all the things I've tried there as well as in the select function:
https://github.com/orlp/glidesort/blob/master/src/util.rs#L1...
I was confident branchless merging could work efficiently. You could say quadsort contributed to the confidence it would work. But I did not use your branchless merge, period.
> So he has no problem giving prior credit, but at least to me, it appears he tries to take prior or co-inventor claim for quadsort's branchless merge techniques and suggests a minimal influence from fluxsort.
I will edit the readme to explicitly mention that glidesort's bidirectional merging is inspired by and an extension of quadsort's parity merge. But you didn't invent the branchless merge, and neither did I. We both came up with our own versions, both after the "Branch Mispredictions Don't Affect Mergesort" paper.
> There is also no mention of the massive performance gain by utilizing the unguarded aspect of quadsort's parity merge for small array sorting. This is at least 20% of glidesort's performance gain.
It's not 20%, at least on my machine. This optimization is precisely what the `--features unstable` flag enables, because this optimization is not sound to do for non-Copy types (and thus needs specialization in Rust). So it's easy to test, for me it's a 11% speedup over the branchless guarded merge: https://github.com/orlp/glidesort/blob/master/src/branchless...
Yes, I also made the guarded merge branchless. I don't believe quadsort does that, because it doesn't have to deal with elements that may not be copied.