Can you sort 10 million numbers using 1MB of memory?

For those of you who have not read the book, Programming Pearls (which you should), this could be new.

The problem is specified as:

   Input: A file containing at most n positive integers, each less than n, where n=107. It is a fatal error if any integer occurs twice in the input. No other data is associated with the integer.

   Output: A sorted list in increasing order of the input integers.

   Constraints: At most  1 MB of storage is available in main memory; ample disk storage is available. The run time can be at most several minutes; a run time of ten seconds need not be decreased.

So how to solve this problem?

Solution 1:

The first and only solution I could think of was use some form of merge sort because merge sort uses a divide and merge technique which is naturally suited to use secondary memory to place the results of the partial sorting that it does. However implementing this is not a simple thing to do.

Solution 2:
(more..)

Read more: Complete Coding

Posted via email from jasper22's posterous