How to sort a large array of ints?

Question

During job interview I was asked the following question:

We have a client application that can send a request and receive a data stream of ints (maybe large, but less than INT_MAX). We need to do this:

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

So I would write the method as follows:

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

The problem is that the large array cannot fit into stack and will be put into heap which decrease performance. How to refactor it in a good-performance way?

Answer 1

Independent of the programming language, the usual way of sorting large amounts of data is the following:

• only sort a chunk of the data
• merge all the sorted chunks using merge sort.

Some optimized implementations even perform insertion sort or something alike on datasets that roughly fit into the CPU's cache (e.g. timsort).

However, since the data does fit into RAM, Java's native implementation should be already pretty much as fast as it gets. If it exceeds RAM, or you want to limit the RAM usage, you'll have to use external sorting. But that is definetely slower, because it goes to disk