Parallel $\mathcal{O}(\sqrt{n})$ Overhead LSD Radix Sort

Robert Clausecker, Florian Schintke

We present Radsort, a variant of LSD radix sort, sorting data with $\mathcal{O}(\sqrt{n})$ additional space. Radsort is stable, admits a simple implementation and is easy to parallel…