Thrust库stable_sort_by_key处理unsigned int时复杂度是否为O(n)？

能否假设stable_sort_by_key处理unsigned int时是O(n)复杂度？ #

不能。Thrust的stable_sort_by_key默认采用比较类排序算法（例如归并排序），这类算法的时间复杂度始终是O(n log n)，和输入数据类型无关——哪怕是unsigned int，只要使用默认实现，就达不到线性时间复杂度。

除自行实现基数排序外，如何保证O(n)复杂度？ #

直接使用Thrust内置的thrust::radix_sort_by_key函数即可：

• 该函数专门针对整数类型（包括unsigned int）实现了稳定基数排序，对于固定位数的整数（如32位unsigned int），排序的迭代次数为常数，整体时间复杂度为O(n)。
• 它完全替代stable_sort_by_key的功能，同时满足稳定性要求，Thrust会根据迭代器的内存空间（主机/设备）自动选择最优的底层实现。

示例代码：

#include <thrust/device_vector.h>
#include <thrust/radix_sort.h>

int main() {
    thrust::device_vector<unsigned int> keys = {3, 1, 4, 1, 5, 9};
    thrust::device_vector<int> values = {0, 1, 2, 3, 4, 5};

    // 稳定线性时间排序
    thrust::radix_sort_by_key(keys.begin(), keys.end(), values.begin());

    return 0;
}

内容的提问来源于stack exchange，提问作者complikator