3 ms·

It is a nice paper, but for practical applications on fixed-size numbers up to 64 bits, as well as for tuples on fixed-size numbers, and for partial sorting, it

It is a nice paper, but for practical applications on fixed-size numbers up to 64 bits, as well as for tuples on fixed-size numbers, and for partial sorting, it does not beat Radix Sort (on moderate-sized arrays). I have tested it in ClickHouse, but end up with this: https://github.com/ClickHouse/ClickHouse/blob/master/src/Common/RadixSort.h https://github.com/ClickHouse/ClickHouse/blob/master/src/Com... PS. It's strange that Google's paper dismisses djbsort: https://sorting.cr.yp.to/ https://sorting.cr.yp.to/ - also in the class of sorting networks, but introduced a few years ago.

Kon-Peki 4y ago
I can't tell from the header file, but does your MSB radix sort use threading? I have a pure C implementation that speeds up radix sort by about 5-6x on my M1 Pro using all 10 cores. I'm struggling to find a way to use SIMD intrinsics to improve upon it, but will be working on Metal and Cuda versions (for my x86 system) to see if that helps. FYI - all I'm doing is changing the algorithm attributed to HH Seward in AoCP 5.2.5 to be MSB, counting the number of elements in each bucket and allocating an equal(ish) number of elements (via entire buckets) to each thread, which then act in the normal recursive manner as described.