Since pdqsort (an older project of mine) was mentioned, I felt it wouldn't be entirely inappropriate to mention that I've since then collaborated with Lukas Bergdoll to provide two high-quality sort implementations for the Rust standard library, ipnsort (unstable) and driftsort (stable).
So if you use Rust, you get these by simply calling [T]::sort(_unstable). Great performance out of the box :)
On my machine (Apple M2), using the benchmarks from the repository on Apple clang 17 and Rust 1.98 nightly:
If it wasn't simple, there would be more lines of code to implement the same idea. As it is, he might have had to spend an hour understanding one line to understand that idea (1 line/hr slow), as opposed to spending an hour reading a hundred lines of code (100 line/hr fast) for the same result.
So if you use Rust, you get these by simply calling [T]::sort(_unstable). Great performance out of the box :)
On my machine (Apple M2), using the benchmarks from the repository on Apple clang 17 and Rust 1.98 nightly:
And now for a cool party trick, let's repeat the 50 million doubles experiment again, but have the first 90% already sorted, last 10% random:Why not compare against that?