Understanding DeepMind's sorting algorithm
Hang on, you can't just quote MB/s numbers for an O(n log(n)) sort. What length were these tests run at?<p>The code size might not end up quite as good (also requires malloc), but a branchless merge sort is a contender for a fast and lightweight sort. Just published, tiny-sort-rs[0] cites 632 bytes and looks like ~350MB/s at 1e4 elements on Zen 3. In my tests, my own pisort[1] benches a little over twice as fast as LongSort, but it uses sorting networks as the base case so it's like 5KB. It's roughly based on piposort[2] which has more complicated recursion but a simpler base case.<p>400 MB/s seems a bit slow for a radix sort on that hardware: I'm hitting those numbers on my i5-6200U, which has less than half the clock rate, with my own radix sort. Recommend checking ska_sort_copy from [3] as it has about the same performance.<p>[0] <a href="https://github.com/Voultapher/tiny-sort-rs">https://github.com/Voultapher/tiny-sort-rs</a><p>[1] <a href="https://github.com/mlochbaum/SingeliSort/blob/master/src/merge.singeli#L136-L152">https://github.com/mlochbaum/SingeliSort/blob/master/src/mer...</a><p>[2] <a href="https://github.com/scandum/piposort">https://github.com/scandum/piposort</a><p>[3] <a href="https://github.com/skarupke/ska_sort">https://github.com/skarupke/ska_sort</a>