TAOCP 5.4.9 Exercise 19

Section 5.4.9: Disks and Drums

Exercise 19. ▶ [25] (B. T. Bennett and A. C. McKellar.) Consider the following approach to keysorting, illustrated on an example file with 10 keys:

i) Original file: $(50,I_0)(08,I_1)(51,I_2)(06,I_3)(90,I_4)(17,I_5)(89,I_6)(27,I_7)(65,I_8)(42,I_9)$ ii) Key file: $(50,0)(08,1)(51,2)(06,3)(90,4)(17,5)(89,6)(27,7)(65,8)(42,9)$ iii) Sorted (ii): $(06,3)(08,1)(17,5)(27,7)(42,9)(50,0)(51,2)(65,8)(89,6)(90,4)$ iv) Bin assignments (see below): $(2,1)(2,3)(2,5)(2,7)(2,8)(2,9)(1,0)(1,2)(1,4)(1,6)$ v) Sorted (iv): $(1,0)(2,1)(1,2)(2,3)(1,4)(2,5)(1,6)(2,7)(2,8)(2,9)$ vi) (i) distributed into bins using (v): Bin 1: $(50,I_0)(51,I_2)(90,I_4)(89,I_6)$ Bin 2: $(08,I_1)(06,I_3)(17,I_5)(27,I_7)(65,I_8)(42,I_9)$ vii) The result of replacement selection, reading first bin 2, then bin 1: $(06,I_3)(08,I_1)(17,I_5)(27,I_7)(42,I_9)(50,I_0)(51,I_2)(65,I_8)(89,I_6)(90,I_4)$

The assignment of bin numbers in step (iv) is made by doing replacement selection on (iii), from right to left, in decreasing order of the second component. The bin number is the run number. The example above uses replacement selection with only two elements in the selection tree; the same size tree should be used for replacement selection in both (iv) and (vii). Notice that the bin contents are not necessarily in sorted order!

Prove that this method will sort, namely that the replacement selection in (vii) will produce only one run. (This technique reduces the number of bins needed in a conventional keysort by distribution, especially if the input is largely in order already.)

Verified: no
Solve time: 24m35s

Solution

We are given a file of (N) records (R_i = (K_i, I_i)) with distinct keys (K_i) (ties can be broken by the index (i)). The algorithm proceeds as follows:

Form key‑index pairs ((K_i, i)) and sort them by key. Let the sorted list be
[ S = \bigl((K_{p_1}, p_1), (K_{p_2}, p_2), \dots, (K_{p_N}, p_N)\bigr),\qquad K_{p_1} < K_{p_2} < \dots < K_{p_N}. ]
Assign bins by replacement selection.
Process the elements of (S) in decreasing order of the index (p_j) (i.e. from the largest original position to the smallest).
Feed them into a replacement‑selection algorithm that uses a priority queue (selection tree) of size (M) (in the example (M=2)).
The algorithm works as follows:
- The first (M) items are inserted with run number (1).
- Current run (r = 1).
- While the queue is not empty:
  - Extract the item of run (r) with the smallest key; output it (its run number is (r)).
  - Read the next input item (x). If (K_x \ge) the key just output, insert (x) with run (r); otherwise insert (x) with run (r+1).
  - If the queue contains no item of run (r), set (r \gets r+1). The run number assigned to each item when it is inserted becomes its bin number (B(i)).
Sort the bin assignments by index and distribute the original records into bins accordingly.
Within each bin the records appear in increasing order of their original index.
Final merge.
Read the bins in decreasing order of bin number (highest bin first, lowest bin last) and apply replacement selection with the same tree size (M).
We must prove that this final replacement selection produces exactly one run.

Proof that the final merge yields a single run

Let the distinct bin numbers produced in step 2 be (1,2,\dots,R).
For each bin (k) define the subsequence [ S_k = \bigl{(K_i,i) \mid B(i)=k\bigr} ] taken in the order of increasing index (i) (this is exactly the order in which the records are stored in bin (k) after step 3).
The final replacement selection receives the concatenated sequence [ S_R ;\Vert; S_{R-1} ;\Vert; \dots ;\Vert; S_1 . ]

We will show that during this final replacement selection the run number never increases beyond (1); hence only one run is produced.

Lemma 1 (Structure of the bins)

If we scan the sorted list (S) from the largest index down to the smallest and perform replacement selection with tree size (M), then for every bin (k) the keys in (S_k) appear in the same relative order as they appear in (S) (i.e. in increasing order of the keys).
Moreover, all keys in bin (k) are strictly smaller than all keys in bin (k+1) for (k=1,\dots,R-1).

Proof.
In the initial replacement selection (step 2) items are inserted in decreasing order of index. Because the input order is a permutation of the sorted list (S), the keys themselves are not processed in sorted order. However, the replacement‑selection algorithm has the well‑known property that the items assigned to the same run are output in increasing order of their keys. Since the algorithm never reorders items within a run, the items of run (k) that are output form a subsequence of the input that is increasing in key. But the input is exactly the elements of (S) taken in some order; therefore the items of run (k) appear in the input in the same order as they appear in (S) (which is increasing key order). Consequently, when we later sort the bin assignments by index, the items inside each bin (S_k) are still in increasing key order.

The second statement is a standard property of replacement selection: when the algorithm finishes run (k) and starts run (k+1), every item that will ever be assigned to run (k+1) has a key strictly larger than every item already assigned to run (k). (Indeed, an item gets run (k+1) only when it arrives with a key smaller than the last output item of run (k); that last output item is the maximum of run (k) because run (k) is output in increasing order. All subsequent items of run (k) are even larger, and all items of run (k+1) are larger than that maximum.) Hence all keys in bin (k) are (<!) all keys in bin (k+1). ∎

Lemma 2 (Invariant of the final merge)

Consider the final replacement selection on (S_R \Vert S_{R-1} \Vert \dots \Vert S_1) with tree size (M).
At any moment, let (C) be the current run number (initially (1)), and let (v) be the key of the last output record (or (-\infty) at the start).
Invariant: The priority queue contains only records of run (C), and every record in the queue has key (\ge v). Moreover, all records that have not yet been read have keys strictly greater than (v).

Proof by induction.
Initially the queue is filled with the first (M) records of (S_R). Because (S_R) is increasing (Lemma 1), all these keys are (\ge) the first key, so (v = -\infty) and the invariant holds.

Assume the invariant holds before a step. We extract the smallest key (u) from the queue (this is the next record of run (C)). By the invariant, (u \ge v). We output (u) and set (v \gets u).

Now we read the next input record. There are two cases:

We are still inside the same bin (S_k).
The next record comes from the same increasing sequence, so its key is (\ge u = v). It is inserted with run (C); the queue still contains only run (C) records, all (\ge v). Unread records in this bin and all earlier bins (which have larger keys by Lemma 1) are (> v).
We have just finished bin (S_k) and move to bin (S_{k-1}) (with (k>1)).
The first record of (S_{k-1}) has a key that is, by Lemma 1, strictly larger than every key in (S_k). Since (v) is the last key output from (S_k), we have (v <) (first key of (S_{k-1})). Thus the new record’s key is (> v), so it is inserted with run (C). All remaining records in (S_{k-1}) and in lower bins are even larger, hence (> v).

In both cases the invariant is preserved. The queue never receives a record with key (< v), so the run number (C) never needs to be incremented. ∎

Since the run number stays (1) throughout, the final replacement selection produces exactly one run. This completes the proof. ∎

Notes

The proof uses only the standard properties of replacement selection:

Items within a run are output in increasing key order.
When a new run starts, all its items have keys larger than every item of the previous run.
The priority queue never needs to hold more than two consecutive runs (here we never even leave run (1) in the final merge).

The algorithm thus sorts the file correctly while using only (M) internal buffer slots for the selection tree in both phases, significantly reducing the number of bins (runs) compared to a naïve distribution sort.