rhsort

pdqsort paper: https://arxiv.org/abs/2106.05123 fluxsort compiles in C++ just fine. Pre-sorted data is just the simplest example of adaptivity. Partially-sorted input can't be tracked easily by the caller and I believe that something like merging a few sorted arrays by concatenating then sorting is pretty common. Fluxsort, glidesort, ipnsort, vergesort all have methods that allow for merging such patterns quickly. According to the benchmarks in the article, many are also doing better at low-cardinality data. If you don't consider any of this adaptivity useful, it's very strange to compare to std::sort which does make some attempt to be adaptive. And strange that your documentation wouldn't mention the difference. But we all know why you're doing that. I suppose you'll keep your fingers in your ears regarding 32-bit radix sort, which has b

I was able to get glidesort running as part of the Robin Hood sort benchmark[1]. See [0]; it's a lot slower than fluxsort on random data. Wondering if I did something wrong. Is cargo build --release with rustc 1.64.0 enough? Tried lto = "thin" in .cargo/config as well, which is ever so slightly faster. Also tried passing in a buffer one, then two, times the input length which didn't change things. Was this tested on x86? Commands to run to replicate my results are below. Clone rhsort and run them in that directory. The res/*.txt results are human-readable but you have to install my programming language[2] to generate the plot. Hey, you made me program in Rust. [0] https://gist.github.com/mlochbaum/7664a046d294dcce2f6cdb1db6... [1] https://github.com/mlochbaum/rhsort [2] https://github.com/mlochbaum/BQN ./wolfbench.sh mkdir res

Here's a sorting algorithm with a similar idea of assuming a random input and applying an idea from hashing (but instead of buckets, it's robin-hood hashing): https://github.com/mlochbaum/rhsort Unlike this post though, it's got proper comparisons against the best C implementations of other algorithms, and is aware that, as most inputs aren't entirely random, its use is very limited.