book cover

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