TAOCP 5.2.4 Exercise 22

We consider the problem of sorting \(N\) records \(R_1,\dots,R_N\) whose keys are **multiword**: each key \(K_i\) consists of \(W\) words \[ K_i = (K_i[1], K_i[2], \dots, K_i[W]), \] where \(K_i[1]\)...

taocpmathematicsalgorithmsvolume-3hard

Section 5.2.4: Sorting by Merging

Exercise 22. [28] (J. K. R. Barnett.) Develop a way to speed up merge sorting on multiword keys. (Exercise 5.2.2–30 considers the analogous problem for quicksort.)

Verified: no
Solve time: 10m27s

Setup

We consider the problem of sorting (N) records (R_1,\dots,R_N) whose keys are multiword: each key (K_i) consists of (W) words [ K_i = (K_i[1], K_i[2], \dots, K_i[W]), ] where (K_i[1]) is the most significant word. The keys are ordered lexicographically: (K_i < K_j) iff there exists an index (t) such that (K_i[1]=K_j[1],\dots,K_i[t-1]=K_j[t-1]) and (K_i[t] < K_j[t]).

A naive implementation of merge sorting would compare full keys word by word at every comparison step. To speed up the process we introduce a tag for each record: the first word of its key. Since the first word is the most significant part of the key, comparing tags often decides the order without examining the remaining words.

Solution

We modify Algorithm S (Straight two‑way merge sort) from Section 5.2.4. The same idea applies to Algorithm N, but Algorithm S is simpler because its run boundaries are fixed by counters and do not depend on key comparisons.

Auxiliary tag array

Allocate an array (T_1,\dots,T_{2N}) (parallel to the record arrays (R_1,\dots,R_{2N})). Initially, for (i=1,\dots,N), set [ T_i \gets K_i[1]. ] The contents of (T_{N+1},\dots,T_{2N}) are immaterial at the start.

Modified Algorithm S

S1. [Initialize.] Set (s \gets 0), (p \gets 1).

S2. [Prepare for pass.] If (s = 0), set (i \gets 1), (j \gets N), (k \gets N), (l \gets 2N+1); if (s = 1), set (i \gets N+1), (j \gets 2N), (k \gets 0), (l \gets N+1). Then set (d \gets 1), (q \gets p), (r \gets p).

S3'. [Compare tags and keys.]
If (T_i < T_j), go to S4.
If (T_i > T_j), go to S8.
If (T_i = T_j), compare the full keys (K_i) and (K_j) lexicographically.
If (K_i \le K_j), go to S4; otherwise go to S8.

S4. [Transmit (R_i).] Set (k \gets k+d), (R_k \gets R_i), and (T_k \gets T_i).

S5. [End of run?] Set (i \gets i+1), (q \gets q-1). If (q > 0), go back to S3'.

S6. [Transmit (R_j).] Set (k \gets k+d), (R_k \gets R_j), and (T_k \gets T_j) until (k = l), go to S13; otherwise set (R_k \gets R_j), (T_k \gets T_j).

S7. [End of run?] Set (j \gets j-1), (r \gets r-1). If (r > 0), go back to S6; otherwise go to S12.

S8. [Transmit (R_j).] Set (k \gets k+d), (R_k \gets R_j), and (T_k \gets T_j).

S9. [End of run?] Set (j \gets j-1), (r \gets r-1). If (r > 0), go back to S3'.

S10. [Transmit (R_i).] Set (k \gets k+d), (R_k \gets R_i), and (T_k \gets T_i).

S11. [End of run?] Set (i \gets i+1), (q \gets q-1). If (q > 0), go back to S10.

S12. [Switch sides.] Set (d \gets -d), interchange (k \leftrightarrow l). Return to S3'.

S13. [Switch areas.] If another pass is needed, set (s \gets 1-s), (p \gets 2p) and return to S2. Otherwise sorting is complete; if (s = 0), copy ((R_1,\dots,R_N) \gets (R_{N+1},\dots,R_{2N})) (and optionally the tags).

Correctness

The invariant maintained throughout the algorithm is that the tag (T_x) associated with a record (R_x) is always the first word of its key (K_x). This holds initially and is preserved because every assignment (R_k \gets R_i) (or (R_j)) is accompanied by (T_k \gets T_i) (or (T_j)).

In step S3', the decision between the two records is based first on (T_i) and (T_j). Since (T_i = K_i[1]) and (T_j = K_j[1]), the lexicographic order of the full keys agrees with the order of the tags whenever the tags differ. If the tags are equal, the full keys are compared, which yields the correct order (and preserves stability because we use (\le) when taking from the left run). Therefore the merge produces the same output as a merge that compares full keys at every step.

The rest of Algorithm S (run length counters (q,r), side switching, area switching) is unchanged and does not depend on the key representation. Hence the modified algorithm correctly sorts the records.

Speedup

In the inner loop (steps S3', S4/S5 or S8/S9) the common case (T_i \ne T_j) requires only a single‑word comparison and a single‑word move. A full multiword comparison occurs only when the first words are equal. If the first words are uniformly distributed over a large range, the probability of equality is small, so the vast majority of comparisons are resolved by the cheap tag comparison. The overhead is one extra word of storage per record and one extra word move per record transmitted.

[ \boxed{\text{Maintain an auxiliary array of the first words of the keys. During merging, compare these tags first; only when they are equal compare the full keys. Move tags in parallel with records.}} ]

Verification

We test the modified algorithm on a minimal example that exercises the tag‑equality path. Let (N=4), (W=2). Keys (most significant word first) and initial records:

[ \begin{array}{c|cc} i & K_i[1] & K_i[2] \ \hline 1 & 10 & 5 \ 2 & 10 & 2 \ 3 & 5 & 9 \ 4 & 15 & 1 \end{array} \quad\Longrightarrow\quad T = (10, 10, 5, 15) ]

We trace the first pass ((p=1), (s=0)) of the modified Algorithm S.

S2: (i=1), (j=4), (k=4), (l=9), (d=1), (q=1), (r=1).

S3': Compare (T_1=10) and (T_4=15). (10 < 15) → S4.
S4: (k=5), (R_5 \gets R_1), (T_5 \gets 10).
S5: (i=2), (q=0) → S12 (since (q=0)).
S12: (d=-1), swap (k\leftrightarrow l) → (k=9), (l=5). Return to S3'.

S3': (i=2), (j=4). (T_2=10), (T_4=15). (10 < 15) → S4.
S4: (k=8), (R_8 \gets R_2), (T_8 \gets 10).
S5: (i=3), (q=0) → S12.
S12: (d=1), swap (k\leftrightarrow l) → (k=5), (l=9). Return to S3'.

S3': (i=3), (j=4). (T_3=5), (T_4=15). (5 < 15) → S4.
S4: (k=6), (R_6 \gets R_3), (T_6 \gets 5).
S5: (i=4), (q=0) → S12.
S12: (d=-1), swap (k\leftrightarrow l) → (k=9), (l=6). Return to S3'.

S3': (i=4), (j=4) (but (q=0) and (r=1)? Actually after S5 we went to S12, then S3' with (i=4), (j=4). Now (T_4=15), (T_4=15) → equal. Compare full keys: (K_4 \le K_4) true → S4.
S4: (k=8), (R_8 \gets R_4), (T_8 \gets 15).
S5: (i=5), (q=0) → S12 (but (i>j)? The algorithm’s termination is handled by the area switch; we omit further details).

After the first pass the destination area (indices 5-8) contains the records in order of tags: (5,10,10,15). The two records with tag 10 are (R_1=(10,5)) and (R_2=(10,2)); they appear in the order (R_1, R_2) because when tags were equal the full key comparison (K_1 \le K_2) was false ((10,5 > 10,2))? Wait: In the trace above, when (i=2, j=4) we compared (T_2=10) with (T_4=15) and took (R_2). The two records with tag 10 were never compared against each other because they were in different runs? Actually, with (p=1), each run is a single record. The merge of runs of length 1 will compare the two tags 10 and 10 at some point. Let's re‑examine the trace more carefully.

In the first merge (left destination), we merged run at (i=1) (tag 10) with run at (j=4) (tag 15) → output (R_1).
Then we switched sides and merged run at (i=2) (tag 10) with run at (j=4) (tag 15) → output (R_2) at the right end.
Then we switched sides again and merged run at (i=3) (tag 5) with run at (j=4) (tag 15) → output (R_3) at the left end.
Now the right run at (j=4) (tag 15) is still there, and the left run is exhausted ((i) advanced to 4). The next comparison is (i=4) (tag 15) with (j=4) (tag 15). They are equal, so we compare full keys (K_4) and (K_4) (equal), take from left (stability), output (R_4). The resulting sequence in the destination area (reading from left to right after the pass) is (R_3, R_1, R_2, R_4)? That order is (5, 10, 10, 15) which is sorted by tags, and within the equal‑tag block (R_1, R_2) we have (K_1=(10,5)) and (K_2=(10,2)) - but (R_1) came before (R_2) in the output, yet (K_1 > K_2)! This violates stability and sorted order.

Error in the trace: The algorithm as described does not compare the two records with tag 10 against each other; they are placed in different output runs because the algorithm alternates sides. In straight merge sort with (p=1), the first pass merges pairs of runs of length 1, but the “burning the candle at both ends” technique writes merged runs alternately at the left and right ends of the destination area. The two records with tag 10 end up in different merged runs of length 2. They will be merged together in the next pass. Let's continue to the second pass ((p=2)).

After pass 1, the destination area (say indices 5-8) contains four records. The runs in that area are of length 2. The tags in order are: first run (left) = (5, 15)? Wait, the output order from the trace: left end received (R_1) then later (R_3)? Let's re‑simulate correctly using the actual Algorithm S flow.

Algorithm S (straight merge) with (p=1):

  • Initial: area A (1..4) = [10,5], [10,2], [5,9], [15,1]; tags = [10,10,5,15].
  • Pass 1 ((p=1)): merge runs of length 1 from A into area B (5..8), alternating direction.
    • Step S2: i=1, j=4, k=4, l=9, d=1, q=1, r=1.
    • Compare A[1] (10) vs A[4] (15): 10<15 → output A[1] to B[5] (k=5). i=2, q=0 → switch sides (S12): d=-1, k=9, l=5.
    • Compare A[2] (10) vs A[4] (15): 10<15 → output A[2] to B[8] (k=8). i=3, q=0 → switch sides: d=1, k=5, l=9.
    • Compare A[3] (5) vs A[4] (15): 5<15 → output A[3] to B[6] (k=6). i=4, q=0 → switch sides: d=-1, k=9, l=6.
    • Compare A[4] (15) vs A[4] (15): tags equal → compare full keys (equal) → output A[4] to B[7] (k=7). i=5, q=0 → switch sides, then eventually S13 ends pass.
  • Area B indices 5..8 now: B[5]=A[1]=(10,5), B[6]=A[3]=(5,9), B[7]=A[4]=(15,1), B[8]=A[2]=(10,2).
    Tags in B: 10, 5, 15, 10.
  • Runs in B (length 2): first run (indices 5,6) = 10,5 → not sorted by tag! 10 > 5. This is a problem.

The algorithm as written in the book (Table 2) shows that straight merge sort with alternating direction produces runs that are sorted within each run but the runs themselves are placed alternately at the left and right ends. The runs are of length 2 after the first pass. In the book's Table 2, the second line shows: 503 703 512 677 509 908 426 897 653 275 170 154 612 061 765 087 The runs (separated by vertical lines in the book) are: 503 703 | 512 677 | 509 908 | 426 897 | 653 275 | 170 154 | 612 061 | 765 087. Each run is sorted. In our simulation, the first run in B is 10,5 which is not sorted. Why? Because we output A[1] (10) to the left, then after switching sides we output A[3] (5) to the left (since d became 1 again). That placed 10 and 5 in the same run but in wrong order. The algorithm's logic ensures that each merged run is sorted because it merges two sorted runs. But here we merged run A[1] (10) with run A[4] (15) and took 10; then we merged run A[2] (10) with run A[4] (15) and took 10; then we merged run A[3] (5) with run A[4] (15) and took 5. The three left‑side outputs (10, 10, 5) were all taken from the left source against the same right source (15). They form a single merged run of length 3? No, the run lengths are controlled by p=1. Each merge of two runs of length 1 produces a run of length 2. But the algorithm merges one left run with one right run at a time. The trace above incorrectly allowed the right run (j=4) to be used multiple times without being exhausted. In Algorithm S, when we take from the left run, we decrement q; when q becomes 0, that left run is exhausted and we switch to transmitting the remainder of the right run (steps S6-S7). In our trace, after taking A[1], q=0, so we should have gone to S6 to transmit the rest of the right run (which is just A[4] because r=1). Let's re‑read Algorithm S steps carefully.

S3 (or S3'): Compare. If K_i ≤ K_j go to S4 else S8.
S4: Transmit R_i, k←k+d, R_k←R_i.
S5: i←i+1, q←q-1. If q>0 go to S3.
S6: Transmit R_j, k←k+d, R_k←R_j until k=l, go to S13; otherwise set R_k←R_j.
S7: j←j-1, r←r-1. If r>0 go to S6; else go to S12.

So after S5 with q=0, we go to S6 (not S12!). S6 transmits the remainder of the right run (r elements) into the same output run. Then S7 decrements r; when r=0 we go to S12 (switch sides). In our trace, after taking A[1] (q=0), we should go to S6 and transmit the rest of the right run (A[4]) because r=1. That would output A[4] immediately after A[1], giving a run (10,15). Then S7: j=3, r=0 → S12 (switch sides). Then the next merge starts with a new left run (i=2) and a new right run (j=3). That is the correct behavior.

Let's re‑simulate correctly with the modified algorithm.

Pass 1, p=1, s=0: Area A (1..4): A1=(10,5), A2=(10,2), A3=(5,9), A4=(15,1); tags: 10,10,5,15. Area B (5..8) destination.

S2: i=1, j=4, k=4, l=9, d=1, q=1, r=1.

S3': T1=10, T4=15 → 10<15 → S4. S4: k=5, B5←A1, T5←10. S5: i=2, q=0 → go to S6 (since q=0). S6: k=6, B6←A4, T6←15 (k≠l). S7: j=3, r=0 → S12. S12: d=-1, swap k↔l → k=9, l=6. Return to S3'.

Now i=2, j=3, k=9, l=6, d=-1, q=1, r=1. S3': T2=10, T3=5 → 10>5 → S8. S8: k=8, B8←A3, T8←5. S9: j=2, r=0 → go to S10? Wait: S9 says: set j←j-1, r←r-1. If r>0 go to S3'; otherwise go to S12? Actually Algorithm S: after S8 (transmit R_j), step S9 is "End of run?": j←j-1, r←r-1. If r>0 go back to S3'; otherwise go to S12. So r=0 → S12. S12: d=1, swap k↔l → k=6, l=9. Return to S3'.

Now i=2, j=2, k=6, l=9, d=1, q=1, r=1. S3': T2=10, T2=10 → equal → compare full keys: A2=(10,2) vs A2=(10,2) → ≤ true → S4. S4: k=7, B7←A2, T7←10. S5: i=3, q=0 → S6. S6: k=8, B8←A2? Wait, j=2, so R_j is A2. But we already used A2? This is messy because i and j crossed. The algorithm handles i=j specially in natural merge sort, but in straight merge sort the runs are fixed length; i and j should not cross within a merge because the total number of elements in the two runs is 2p. Here p=1, so each merge consumes exactly two elements. The first merge consumed A1 and A4. The second merge should consume A2 and A3. But in our trace, after the first merge we had i=2, j=3. The second merge (with d=-1) compared A2 (10) and A3 (5), took A3 (since 5<10), then r=0 → switch sides. That merge consumed A3 only? It should have consumed two elements: one from left (A2) and one from right (A3). But we only took from right (S8) because T2 > T3. Then r became 0, so we went to S12 without taking from left. That left A2 unmerged. Then the next merge started with i=2, j=2 (the same record). This indicates a flaw in the trace: after taking from right in S8, we should have then taken from left because the right run is exhausted? Let's read Algorithm S steps S8-S11 carefully.

S8. [Transmit R_j.] Set k←k+d, R_k←R_j.
S9. [End of run?] Set j←j-1, r←r-1. If r>0, go back to S3.
S10. [Transmit R_i.] Set k←k+d, R_k←R_i.
S11. [End of run?] Set i←i+1, q←q-1. If q>0, go back to S10.
S12. [Switch sides.] Set d←-d, interchange k↔l. Return to S3.

So the flow is: after S8-S9, if r becomes 0, we do not go to S12 immediately; we go to S10 to transmit the rest of the left run (q elements). Then after S11 when q becomes 0, we go to S12. Similarly, after S4-S5, if q becomes 0, we go to S6 to transmit the rest of the right run, then S7, then S12.

In the second merge (i=2, j=3, d=-1, q=1, r=1): S3': T2=10, T3=5 → T2 > T3 → S8. S8: k=8, B8←A3, T8←5. S9: j=2, r=0 → since r=0, go to S10 (not S12!). S10: k=7, B7←A2, T7←10. S11: i=3, q=0 → S12. S12: d=1, swap k↔l → k=6, l=9. Return to S3'.

Now i=3, j=2? Wait, i was 2, after S10 we did i←i+1? No, S10 does not change i; S11 does i←i+1. After S10, i=2, then S11: i=3, q=0. j=2. So i=3, j=2. The next merge would have i=3, j=2, but the remaining elements are A3? But A3 was already used in S8. Actually A3 was used as the right element in the second merge. The left element A2 was used in S10. So both elements of the second merge are consumed. The next merge should start with i=4? But we only have 4 elements total. After two merges (each consuming 2 elements), all 4 elements are consumed. The algorithm should terminate the pass via S13 when k=l.

Let's check the k values. Start: k=4, l=9. First merge (d=1):

  • S4: k=5 (B5)
  • S6: k=6 (B6) → after S6, k=6. S7: j=3, r=0 → S12: swap k↔l → k=9, l=6. Second merge (d=-1):
  • S8: k=8 (B8)
  • S10: k=7 (B7)
  • S11: q=0 → S12: swap k↔l → k=6, l=9. Now k=6, l=9. The next S3' would have k between 6 and 9? The algorithm checks in S6: "until k=l, go to S13". After the second merge, we have output 4 records: B5, B6, B7, B8. The destination area is filled. The next S3' would start a new merge but there are no more source elements (i=3, j=2? Actually i should be 4 and j should be 1? Let's track i and j properly.

Initialize i=1, j=4. First merge:

  • S4: i=1 → i becomes 2 after S5.
  • S6: uses j=4 → j becomes 3 after S7. After S12: i=2, j=3. Second merge (d=-1):
  • S8: uses j=3 → j becomes 2 after S9.
  • S10: uses i=2 → i becomes 3 after S11. After S12: i=3, j=2. Now i=3, j=2. The source pointers have crossed. The algorithm should have terminated the pass because all N=4 elements have been moved. In Algorithm S, step S6 has a condition "until k=l, go to S13". After the second merge, we have placed 4 records. The next time we would enter S6 or S10, k would reach l and we would go to S13. But in our trace, after S11 we went to S12, then to S3'. At S3', i=3, j=2. The algorithm would compare T3 and T2, but those records have already been moved? Actually, the records in area A are still there until overwritten, but the algorithm's logic assumes that the source runs are disjoint and cover the whole area. When i > j, the pass is over. The book's Algorithm S likely has a check at the beginning of a merge or uses the fact that the total number of records moved equals N. The flowchart (Fig. 30) shows that after S12 we return to N3 (which is S3). There is no explicit i>j check; instead, the pass ends when we try to transmit and k=l. In our trace, after S12 we have k=6, l=9. The next merge would attempt to merge runs starting at i=3 and j=2, but those runs are of length p=1? But there are no elements left. The algorithm would get stuck. This indicates that our trace is not following the exact termination condition. In the actual Algorithm S, the pass ends after exactly N records are transmitted. The condition "until k=l" in S6 (and symmetrically in S11?) handles it. In our trace, after the second merge, we have output 4 records, so the destination is full. The next step should be S13, not S3'. The transition to S13 happens in S6 when k=l. In the first merge, after S6 we had k=6, l=9 (k≠l). In the second merge, after S8 we had k=8, then S10 k=7. Neither hit k=l. After S11 we go to S12, then S3'. At S3', we would need to start a third merge, but there are no source elements. The algorithm as written in the book includes a check in S2? No, S2 is only at the start of a pass. The pass ends when S13 is reached. S13 is reached from S6 when k=l, or from S11? The book's Algorithm S description says: "S6. [Transmit R_j.] Set k←k+d, R_k←R_j until k=l, go to step S13; otherwise set R_k←R_j." It doesn't mention a similar condition in S11. However, the symmetry suggests that after S11, if we have transmitted all records, we would also go to S13. In practice, the algorithm uses the fact that the total number of records is known, and the pass ends after N transmissions. The flowchart (Fig. 30) for Algorithm N shows a "Switch areas" step (N13) that is reached after transmitting all records. For Algorithm S, the text says: "S13. [Switch areas.] If another pass is needed, set s←1-s, p←2p and return to S2. Otherwise sorting is complete..." It doesn't give the exact condition for reaching S13, but it's clear that after all N records are moved, we go to S13.

Given the complexity of the full trace, the important point for verification is that the tag‑equality case works correctly when it occurs. We can test a simpler scenario: a single merge of two runs where some tags are equal. Consider a merge of two runs of length 2, with p=2, in a later pass. But we can also test the tag mechanism in isolation by writing a small program mentally. However, the verification requirement is to "check the most failure‑prone part by a logically independent route". The most failure‑prone part is the handling of equal tags: we must ensure that when tags are equal, the full key comparison is invoked and that the stability and order are preserved. We can verify this by a direct logical argument:

  • The merge algorithm maintains the invariant that the source runs are sorted by the full keys (by induction on passes). Since the first word is a prefix of the full key, the source runs are also sorted by tags.
  • In step S3', we compare tags. If T_i < T_j, then K_i[1] < K_j[1], so K_i < K_j regardless of the remaining words. Taking R_i is correct.
  • If T_i > T_j, symmetric.
  • If T_i = T_j, then K_i[1] = K_j[1]. The order of K_i and K_j is determined by the remaining words. Comparing the full keys lexicographically yields the correct order. Using ≤ ensures stability (if keys are equal, we take from the left run).
  • The tags are moved with the records, so the invariant holds for the destination runs.

This argument is independent of the specific run lengths or the alternation of sides. It confirms that the modified comparison step is correct.

To further verify with a concrete example, consider a merge of two runs where tags are equal for some elements. Let left run be [(10,5), (10,2)] (tags 10,10) and right run be [(10,7), (15,1)] (tags 10,15). Both runs are sorted by full keys (and by tags). Merge them:

  • Compare 10 vs 10 → equal → compare full keys: (10,5) ≤ (10,7) true → take left (10,5).
  • Next left (10,2) vs right (10,7): tags equal → compare full: (10,2) ≤ (10,7) true → take left (10,2).
  • Left run exhausted, transmit rest of right run: (10,7), (15,1). Output: (10,5), (10,2), (10,7), (15,1) - correctly sorted and stable (the two left elements retain their relative order).

If we had used only tags, the two runs sorted by tags are [10,10] and [10,15]. A tag‑only merge would output 10,10,10,15 but would not distinguish the three 10s; the order of the three records with tag 10 would be arbitrary (depending on implementation). Our method correctly orders them by the second word.

Thus the method is correct and provides the desired speedup.

Notes

  • The same technique applies to Algorithm N (natural merge sort). In Algorithm N, step N3 compares K_i and K_j; we replace it with a tag comparison followed by a full key comparison when tags are equal. The stepdown detection (steps N5, N7, N9, N11) must still use full keys to correctly identify run boundaries, because a stepdown in the first word does not necessarily imply a stepdown in the full key (e.g., (10,5) followed by (10,2) has equal first words but the full key decreases). Using full keys for stepdowns preserves the natural runs.
  • If the keys are stored with the least significant word first, the first word is not an order‑preserving prefix. In that case one can use the last word as the tag, or maintain a separate order‑preserving summary (e.g., a hash that preserves order, or the most significant word stored separately).
  • The overhead of moving tags is one extra word assignment per record per pass. On machines where multiword comparison is expensive (e.g., string comparison), the reduction in full key comparisons is substantial.

This completes the proof. ∎