Radix sorting is great, as this article points out. But I followed the links and didn't see any mention of the most obvious optimization that makes it even bet

Radix sorting is great, as this article points out. But I followed the links and didn't see any mention of the most obvious optimization that makes it even better on modern systems. If you do MSB for the first pass, then the subsequent passes within each bucket are completely independent :) So... Choose a large radix and do one MSB pass, then parallelize the LSB processing of each bucket. This is fantastic on a GPU. You might think that you would want many thousands of kernels running simultaneously, but in actuality each SM (and the Apple equivalent) has a thread-local cache, so you really only want a couple hundred simultaneous kernels at the most. I've written CUDA and Metal versions and they are fast. And you don't even have to be very good at GPU programming to get there. It's very basic. AoCP has the pseudocode.