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

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 parallelise. For arrays exceeding a size of around 2 MiB it outperforms a conventional out-of-place LSD radix sort.