Parallel $\mathcal O(\sqrt n)$ Overhead LSD Radix Sort
2026-07-06 • Data Structures and Algorithms
Data Structures and AlgorithmsDatabases
AI summaryⓘ
The authors introduce Radsort, a new version of the LSD radix sort algorithm that uses less extra memory, specifically around the square root of the input size. Their method keeps the order of equal elements (stable), is simple to implement, and works well with parallel processing. They found that for large arrays (bigger than about 2 million elements), Radsort runs faster than traditional LSD radix sort that uses extra space. Overall, the authors show a practical way to improve sorting efficiency with less memory overhead.
LSD radix sortstable sortingparallel algorithmsmemory usagesorting algorithmsout-of-place sortingalgorithm complexityarray sorting
Authors
Robert Clausecker, Florian Schintke
Abstract
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.