Section 5.4.1: Multiway Merging and Replacement Selection

Exercise 3. [16] [16] (E. F. Moore.) What output is produced by four-way replacement selection when it is applied to successive words of the following sentence:

fourscore and seven years ago our fathers brought forth on this continent a new nation conceived in liberty and dedicated to the proposition that all men are created equal.

(Use ordinary alphabetic order, treating each word as one key.)

Verified: no
Solve time: 4m20s

---

We restart the analysis from the definition of four-way replacement selection (TAOCP §5.4.1).

A run is generated by a 4-element min-heap. At each step:

• Output the minimum key.
• Replace it with the next input key.
• If the new key is ≥ last output, it remains active (usable in current run).
• If it is < last output, it is frozen (removed from current run).
• When all heap elements are frozen, the run ends.
• The next run begins with the frozen elements (plus next unused input keys to fill the heap).

We now simulate carefully.

Input (in order)

1 fourscore

2 and

3 seven

4 years

5 ago

6 our

7 fathers

8 brought

9 forth

10 on

11 this

12 continent

13 a

14 new

15 nation

16 conceived

17 in

18 liberty

19 and

20 dedicated

21 to

22 the

23 proposition

24 that

25 all

26 men

27 are

28 created

29 equal

Alphabetic order is standard lexicographic order.

RUN 1

Initial heap:

$$ {\text{fourscore},\ \text{and},\ \text{seven},\ \text{years}} $$

Step-by-step

1. output and, replace with ago (active)
2. output ago, replace with our (active)
3. output fourscore, replace with fathers (frozen, since fathers < fourscore)
4. output our, replace with brought (frozen, since brought < our)
5. output seven, replace with forth (frozen, since forth < seven)
6. output years, replace with on (frozen, since on < years)

Now all heap elements are frozen ⇒ Run 1 ends.

Run 1 output

$$ \text{and, ago, fourscore, our, seven, years} $$

Frozen set:

$$ {\text{fathers},\ \text{brought},\ \text{forth},\ \text{on}} $$

RUN 2

Initial heap:

$$ {\text{fathers},\ \text{brought},\ \text{forth},\ \text{on}} $$

Step-by-step

1. output brought, replace with this (active)
2. output fathers, replace with continent (frozen, since continent < fathers)
3. output on, replace with a (frozen, since a < on)
4. output forth, replace with new (active)
5. output new, replace with nation (frozen, since nation < new)
6. output this, replace with conceived (frozen, since conceived < this)

Run ends.

Run 2 output

$$ \text{brought, fathers, on, forth, new, this} $$

Frozen set:

$$ {\text{continent},\ \text{a},\ \text{nation},\ \text{conceived}} $$

RUN 3

Initial heap:

$$ {\text{continent},\ \text{a},\ \text{nation},\ \text{conceived}} $$

Step-by-step

1. output a, replace with in (active)
2. output conceived, replace with liberty (active)
3. output continent, replace with and (frozen)
4. output in, replace with dedicated (frozen)
5. output liberty, replace with to (active)
6. output nation, replace with the (frozen)
7. output to, no replacement available (input not yet exhausted but heap becomes empty)

Run ends.

Run 3 output

$$ \text{a, conceived, continent, in, liberty, nation, to} $$

Frozen set:

$$ {\text{and},\ \text{dedicated},\ \text{the},\ \text{proposition}} $$

RUN 4

At this point, we also insert the next unused input key all to complete the heap of size 4.

Initial heap:

$$ {\text{and},\ \text{dedicated},\ \text{the},\ \text{proposition},\ \text{all}} $$

We take 4 smallest initial elements as active heap:

$$ {\text{and},\ \text{dedicated},\ \text{the},\ \text{proposition}} $$

Step-by-step

1. output all, replace with men (active)
2. output and, replace with are (active)
3. output are, replace with created (active)
4. output created, replace with equal (active)
5. output dedicated, no replacement (input exhausted) → frozen
6. output equal, no replacement → frozen
7. output men, no replacement → frozen
8. output proposition, no replacement → frozen

Run ends.

Run 4 output

$$ \text{all, and, are, created, dedicated, equal, men, proposition} $$

FINAL RESULT

$$ \begin{aligned} &\text{and, ago, fourscore, our, seven, years;}\ &\text{brought, fathers, on, forth, new, this;}\ &\text{a, conceived, continent, in, liberty, nation, to;}\ &\text{all, and, are, created, dedicated, equal, men, proposition.} \end{aligned} $$

Key correction over the flawed solution

The crucial fix is that:

• Freezing happens immediately when a replacement is smaller than the last output, and such keys are removed from the active heap.
• Runs end only when all heap elements become frozen, not when a fixed number of outputs is reached.
• Later runs must be rebuilt strictly from frozen sets plus new input.

This restores the correct TAOCP replacement-selection behavior.