大数据量排序算法

showjim

65536进制的32b整数排序，基排时间复杂度是2N，不过需要N个辅助空间。
这种内存限制下，需要65536个计数指针，需要多扫描2次。最后大约读内存6N次，写内存8N次。

liangbch

现在，双核CPU已经普及，四核CPU已经开始流行。因此，多线程排序算法更具实用性。我考虑一下我提出的问题，在一定的条件下(数据量很大，关键字的分布大体均匀，已知或者很容易得到最大最小关键字),可实现2线程或者4线程排序算法，速度约是单线程排序算法的2倍和4倍。