Precise Problem Statement
(Section 1.2 of
Programming Pearls)
To the programmer these requirements
added up to,
``How do I sort a disk file?''
Before we attack the problem,
let's arrange what we know in a less biased and more useful form.
-
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 (roughly) a megabyte 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.
Think for a minute about this problem specification.
How would you advise the programmer now?
Next: Section 1.3. Program Design.
Copyright © 1999
Lucent Technologies. All rights reserved.
Thu 23 Sep 1999