to SORT 1 BILLION of integer numbers with small physical memory

Question

Want to SORT 1 BILLION of integer numbers and my system has just 1 GB of RAM.What could be the fastest and efficient way to sort?

1. Say we have an input in a text file an integer per line.

2. We are using java program to sort.

3. I have specified RAM as we cannot hold all the input integers in the RAM.

Update: Integers are 7 digit numbers.

Answer 1

Integers are 7 digit numbers.

So there are only 10 million possible values.

You have 1GB of RAM. Make an array of counters, one for each possible value.

Read through the file once, count up the counters.

When done, output the numbers according to the final counter values.

Every number can occur at most 1 billion times. So a 32bit counter would be enough. This means a 10M x 4 bytes = 40M byte array.

Answer 2

The simplest thing to do is break the input into smaller files that can fit in memory and sort each, and then merge the results.

Guido van Rossum has a good description of doing this in python while obviously not the same language the principle is the same.