Parallel O(sqrt n) Overhead LSD Radix Sort
Summary
The paper introduces Radsort, a variant of LSD radix sort with O(sqrt(n)) additional space. It is stable, simple to implement, and easily parallelizable, with performance advantages for data sizes above roughly 2 MiB compared to conventional in-place LSD radix sort. The article details its characteristics, context, and references, highlighting potential impact on large-scale sorting tasks.