Radix Sort

原始题目：LeetGPU - Radix Sort

题目描述

在 GPU 上实现基数排序算法，对 32 位无符号整数数组升序排列。必须使用基数排序算法（而非其他排序）。

实现要求

• 不允许使用外部库。
• solve 函数签名必须保持不变。
• 最终排序结果必须存储在 output 数组中。

示例

Input:  [5, 2, 8, 1, 9, 4]
Output: [1, 2, 4, 5, 8, 9]

约束条件

• $1 \le N \le 1{,}000{,}000$。

解题思路

GPU 基数排序的经典实现是LSD（最低位优先）基数排序：每次按 4 个 bit（一个十六进制数位）分桶，共 8 轮（32/4）。每轮包含：计数（直方图统计每个桶的元素数）、前缀和（确定每个桶的输出偏移）、散射写入（按桶偏移重排）。计数步骤使用了原子操作或分块本地直方图，前缀和使用并行 scan。GPU 基数排序已被广泛研究（如 Merrill & Grimshaw 的经典论文），是 Thrust/CUB 库的标准实现。欢迎在 GitHub Discussions 分享你的解法。