作者提出Radsort，一种稳定的LSD基数排序变体，仅使用O(sqrt(n))额外空间且易于并行化。对于大于约2 MiB的数组，其性能优于传统非原地LSD基数排序。
背景
LSD基数排序是一种广泛应用的非比较排序算法，但传统实现需要O(n)额外空间。本研究解决了并行排序场景中的空间效率瓶颈。
- 来源
- Lobsters
- 发布时间
- 2026年8月31日 05:57
- 评分
- 6.0 / 10
作者提出Radsort，一种稳定的LSD基数排序变体，仅使用O(sqrt(n))额外空间且易于并行化。对于大于约2 MiB的数组，其性能优于传统非原地LSD基数排序。
LSD基数排序是一种广泛应用的非比较排序算法，但传统实现需要O(n)额外空间。本研究解决了并行排序场景中的空间效率瓶颈。