Impressive!

There are already implementations of sample sorting that are much faster than c++ sort (but I don't recall how much faster). I'd be very interested in a comparison to some of those...

Also, since we are sorting integers, I'd also be interested to know how well a modern implementation of radix sort can be made.

:) Are you thinking of ips4o (sample sort)? That's about 2-3x std::sort. There's also a pending patch to std::sort that replaces it with BlockQuicksort which would narrow that gap.

We integrate vqsort into ips4o, calling it once subarrays fit in L2. That speeds up ips4o by 2.9x (single thread) and 1.6 (parallel - bandwidth limited). More details in the paper.

I previously also worked on radix sort: https://arxiv.org/abs/1008.2849 Interestingly, that 12 year old result on dual-socket/8 cores is only about twice as fast as a single AVX-512 core today.

Also discussed here: https://news.ycombinator.com/item?id=31622548

100x faster: Don't sort.

Fair :) Sorting is useful in DB joins/group-by, though.

(Author here, happy to discuss.)

At first glance seems like a snarky dismissal, but this is actually valid, actionable advice. If you can arrange your data flow in such a way that sorting is unnecessary, you've avoided an expensive optimization problem altogether.

No sorting is faster than no sorting.