如何对大量的int进行排序？

Question

在求职面试中,我被问到以下问题:

我们有一个客户端应用程序可以发送请求并接收一个int数据流(可能很大,但小于INT_MAX).我们需要这样做:

Int Data  ----> Our  ----> Sorted Int Data
Stream          App        Data Stream

所以我会按如下方式编写方法:

public int[] sort(int[] array){
   Arrays.sort(array);
   return array;
}

问题是大的 array不能装入堆栈并将被放入堆中,这会降低性能.如何以良好的性能重构它？

Answer 1

独立于编程语言,通常的方法是对大量数据进行排序如下:

• 只排序一大块数据
• 使用合并排序合并所有排序的块.

一些优化的实现甚至可以对大致适合CPU缓存的数据集执行插入排序或类似的操作(例如,timsort).

但是,由于数据确实适合RAM,因此Java的本机实现应该已经快得多了.如果它超过RAM,或者您想限制RAM使用,则必须使用外部排序.但这确实比较慢,因为它会进入磁盘