200-300位整数的最快整数排序实现？

Question

对于200-300位大小的整数,最快的整数排序实现是什么？精确的int大小是固定的; 我有这样的整数高达2千兆字节(全部在RAM中).

我听说可以在O(n log log M)或甚至O(n sqrt(log log M))时间平均排序这样的集合,其中n是整数,M是最大整数.内存使用量有限(我可能会额外使用0.5-1 GB).排序可以就地进行; in可能不稳定(重新排序重复).

是否有这种排序方法的C/C++实现,例如Han&Thorup(2002)？

Answer 1

基数排序可用于对具有固定大小键的数据进行排序。由于这种条件并不经常满足，所以该技术没有被过多讨论，但当考虑到密钥大小时，它可以是 O(n)。