Programming-Pearls-source-code/sec012.html at master · ericwang14/Programming-Pearls-source-code · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
<HTML>
<HEAD>
<title>Precise Problem Statement</title>
</HEAD>

<BODY BGCOLOR=#ffffff>
<a href="index.html">
<img alt="book cover" ALIGN=right hspace=20 src="pp2e.jpg">
</a>
<P>
<h1>Precise Problem Statement
<br>(Section 1.2 of
<br><font color="#a52a2a">Programming Pearls</font>)
</h1>


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.
<DL>
<DT>
<i>Input</i>:
<DD>
A file containing at most <i>n</i> positive integers,
each less than <i>n</i>,
where <i>n</i> = 10<sup>7</sup>.
It is a fatal error if any integer
occurs twice in the input.
No other data is associated with the integer.

<br><br><DT>
<i>Output</i>:
<DD>
A sorted list in increasing order of the input integers.

<br><br><DT>
<i>Constraints</i>:
<DD>
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.
</DL>

<br>
Think for a minute about this problem specification.
How would you advise the programmer now?


<p><a href="sec013.html">Next: Section 1.3. Program Design.</a>

<p>
<FONT SIZE=1>Copyright &#169; 1999
<B>Lucent Technologies.</B> All rights reserved.</FONT>
<font size=-2>
Thu 23 Sep 1999
</BODY>
</HTML>