TAOCP 5 Exercise 24

**Solution** We are given \(N = 3\,000\,000\) distinct names \(x_1, x_2, \dots, x_N\) arranged geographically from east (\(x_1\)) to west (\(x_N\)).

taocpmathematicsalgorithmsvolume-3hard

Section 5: Introduction to Sorting

Exercise 24. ▶ [30] Three million men with distinct names were laid end-to-end, reaching from New York to California. Each participant was given a slip of paper on which he wrote down his own name and the name of the person immediately west of him in the line. The man at the extreme western end didn't understand what to do, so he threw his paper away; the remaining 2,999,999 slips of paper were put into a huge basket and taken to the National Archives in Washington, DC, where the contents of the basket were shuffled completely and transferred to magnetic tapes.

At this point an information scientist observed that there was enough information on the tapes to reconstruct the list of people in their original order. And a computer scientist discovered a way to do the reconstruction with fewer than 1000 passes through the data tapes, using only sequential accessing of tape files and a small amount of random-access memory. How was that possible?

In other words, given the pairs $(x_i, x_{i+1})$, for $1 \le i < N$, in random order, where the $x_i$ are distinct, how can the sequence $x_1, x_2, \ldots, x_N$ be obtained, restricting all operations to serial techniques suitable for use with magnetic tapes? This is the problem of sorting into order when there is no easy way to tell which of two given keys precedes the other; we have already raised this question as part of exercise 2.2.3–25.]

Verified: yes
Solve time: 1h19m

Solution

We are given (N = 3,000,000) distinct names (x_1, x_2, \dots, x_N) arranged geographically from east ((x_1)) to west ((x_N)). The input consists of the (N-1) unordered pairs ((x_i, x_{i+1})) for (i = 1, \dots, N-1), stored on magnetic tape in random order. We may only access tapes sequentially and have a small amount of random‑access memory (a few tape blocks for buffers). The goal is to output the sequence (x_1, x_2, \dots, x_N) on tape using fewer than (1000) passes over the data.

1. Representation

A chain is a contiguous subsequence of the original path, stored as a sequence of names in east‑to‑west order. Initially each pair ((x_i, x_{i+1})) forms a chain of length (2). The set of chains always forms a partition of the path into disjoint segments. For a chain (C) we denote its first element by (\operatorname{start}(C)) and its last element by (\operatorname{end}(C)). Chains are stored on tape as consecutive blocks of names; we can read a chain sequentially from its start to its end.

2. Algorithm

The algorithm repeatedly merges chains that are adjacent in the original path. At each iteration we have a collection of chains. We perform the following steps:

  1. Sort by start - Using an external merge sort, sort all chains by their (\operatorname{start}(C)) key (using an arbitrary total order on names, e.g. lexicographic). Write the sorted chains to tape (S_{\text{start}}).
  2. Sort by end - Similarly, sort all chains by their (\operatorname{end}(C)) key. Write the sorted chains to tape (S_{\text{end}}).
  3. Merge adjacent chains - Sequentially read (S_{\text{end}}) and (S_{\text{start}}). Maintain current chains (A) from (S_{\text{end}}) and (B) from (S_{\text{start}}).
    • If (\operatorname{end}(A) = \operatorname{start}(B)): (A) and (B) are adjacent. Concatenate them to form a new chain (C = A \circ B) (write all names of (A), then all names of (B) except its first, which equals (\operatorname{end}(A))). Write (C) to a new output tape. Advance both tapes.
    • If (\operatorname{end}(A) < \operatorname{start}(B)): (A) has no successor in the current set. Write (A) to the output tape unchanged. Advance (S_{\text{end}}).
    • If (\operatorname{end}(A) > \operatorname{start}(B)): (B) has no predecessor. Write (B) to the output tape unchanged. Advance (S_{\text{start}}). Continue until both tapes are exhausted. The output tape now contains the new set of chains.
  4. Replace the current set of chains with the newly created chains. If only one chain remains, stop; otherwise repeat from step 1.

After the loop terminates, the single chain on the output tape contains all (N) names in the correct geographic order (x_1, x_2, \dots, x_N). Write this chain to the final output tape.

3. Handling the Missing Pair

The original data lacks a pair for (x_N) because the westernmost man discarded his slip. Consequently, no chain initially starts with (x_N), and no chain ends with (x_1). The merge step naturally handles this: the chain ending with (x_N) will never find a successor (since no chain starts with (x_N)), so it is passed through unchanged. The chain starting with (x_1) will never find a predecessor, so it is also passed through. No dummy chains are needed.

4. Pass Count Analysis

Let (N = 3,000,000). The number of initial chains is (M_1 = N-1). Each merge iteration reduces the number of chains by at least a factor of (2) (each merge combines two chains, and at most two chains - the head and the tail - remain unmerged). Thus after (k) iterations the number of chains (M_k) satisfies (M_k \le \lceil M_1 / 2^{k-1} \rceil). The process stops when (M_k = 1), which occurs after at most (K = \lceil \log_2 N \rceil = 22) iterations.

An external merge sort on (M) records (chains) requires (\lceil \log_2 M \rceil) passes over the data (each pass reads and writes all records once). In iteration (k) we perform:

  • Two sorts (by start and by end): (2 \lceil \log_2 M_k \rceil) passes.
  • One sequential merge pass: (1) pass.

Total passes in iteration (k): (2 \lceil \log_2 M_k \rceil + 1).

Summing over (k = 1) to (K): [ \sum_{k=1}^{K} \bigl(2 \lceil \log_2 M_k \rceil + 1\bigr) \le 2 \sum_{j=0}^{K-1} \lceil \log_2 N - j \rceil + K. ] Since (\lceil \log_2 N \rceil = 22), the sum is bounded by [ 2 \sum_{i=1}^{22} i + 22 = 2 \cdot \frac{22 \cdot 23}{2} + 22 = 506 + 22 = 528. ] The initial reading of the input to form the first chains is included in the first iteration’s sorts. The final output of the single chain adds at most one more pass. Thus the total number of passes is at most (529 < 1000).

All operations are purely sequential on tape files; the random‑access memory required is only a few blocks for merge buffers. During concatenation we stream the chains from the input tapes to the output tape, never needing to hold an entire chain in memory.

5. Correctness Proof

Invariant. At the beginning of each iteration (after the first merge), the chains form a partition of the set ({x_1, \dots, x_N}) into contiguous segments in the correct geographic order.

Base case (after first iteration).
The input provides the (N-1) pairs ((x_i, x_{i+1})). Sorting them by first component and by second component and then merging as described produces a set of chains. Because the merge concatenates exactly those pairs that share an endpoint, the resulting chains are disjoint and cover all names exactly once. The chain starting with (x_1) has no predecessor, the chain ending with (x_N) has no successor, and every other chain has both. Thus the invariant holds.

Inductive step.
Assume the invariant holds at the start of some iteration. The chains are a partition of the path into contiguous segments in correct order. Therefore each chain has at most one successor (the chain whose start equals its end) and at most one predecessor.
We sort the chains by start and by end. The merge step compares (\operatorname{end}(A)) and (\operatorname{start}(B)):

  • If (\operatorname{end}(A) = \operatorname{start}(B)), then (A) and (B) are adjacent in the path. Concatenating them (removing the duplicate shared name) yields the correct longer segment.
  • If (\operatorname{end}(A) < \operatorname{start}(B)), then (A) has no successor; it is the current tail segment. It is passed through unchanged.
  • If (\operatorname{end}(A) > \operatorname{start}(B)), then (B) has no predecessor; it is the current head segment. It is passed through unchanged.

Because the chains partition the path, every adjacent pair is merged exactly once, and the head and tail are preserved. The output chains again form a partition of the path into contiguous segments in correct order, with roughly half as many chains. Hence the invariant holds for the next iteration.

Termination.
After (K = \lceil \log_2 N \rceil) iterations we have (M_K = 1). The single chain must contain all (N) names in the correct geographic order (x_1, x_2, \dots, x_N).

6. Remarks

The algorithm uses only equality tests on names and an arbitrary total order for sorting; no geographic comparison is required. All tape operations are sequential; the random‑access memory needed is limited to a few tape blocks for merge buffers. The total number of passes is well below (1000), satisfying the problem’s constraint.