The authors present Radsort, a stable LSD radix sort variant that uses only O(sqrt(n)) additional space while being easy to parallelize. For arrays larger than ~2 MiB, it outperforms conventional out-of-place LSD radix sort.
Background
LSD radix sort is a widely used comparison-free sorting algorithm, but traditional implementations require O(n) additional space. This work addresses the space-efficiency bottleneck in parallel sorting scenarios.
- Source
- Lobsters
- Published
- Aug 31, 2026 at 05:57 AM
- Score
- 6.0 / 10