TAOCP 5.2.4 Exercise 15

The redundancy occurs in the main merge loop of Algorithm L.

taocpmathematicsalgorithmsvolume-3medium

Section 5.2.4: Sorting by Merging

Exercise 15. [20] Hand simulation of Algorithm L reveals that it occasionally does redundant operations; the assignments $|L_s| \leftarrow p$, $|L_s| \leftarrow q$ in steps L4 and L6 are unnecessary about half of the time, since we have $L_s = p$ (or $q$) each time step L4 (or L6) returns to L3. How can Program L be improved so that this redundancy disappears?

Verified: no
Solve time: 2m51s

Solution

The redundancy occurs in the main merge loop of Algorithm L. The original steps (inferred from the exercise statement) are:

L3 Compare keys (K_p) and (K_q). If (K_p \le K_q) go to L4, otherwise go to L6.
L4 Set (|L_s| \leftarrow p), (s \leftarrow p), (p \leftarrow |L_p|). Go to L3.
L6 Set (|L_s| \leftarrow q), (s \leftarrow q), (q \leftarrow |L_q|). Go to L3.

When several consecutive elements are taken from the same list, say the (p)-list, the sequence L4 → L3 → L4 occurs. After the first L4 we have (s = p_{\text{old}}) and (p = |L_{p_{\text{old}}}| = p_{\text{new}}). Because the input list is linked, (|L_s| = |L_{p_{\text{old}}}| = p_{\text{new}} = p). Hence the assignment (|L_s| \leftarrow p) in the second L4 writes the same value that is already there. The same redundancy appears in L6.

To eliminate it we replace each of L4 and L6 by a short loop that continues to take elements from the current list as long as its key remains (\le) (resp. (>)) the other list’s key. The link assignment is performed only once - when we switch to the other list.

Improved algorithm (only the changed steps are shown; the rest of Algorithm L is unchanged):

L3 Compare (K_p) and (K_q). If (K_p \le K_q) go to L4, otherwise go to L6.

L4 Set (|L_s| \leftarrow p), (s \leftarrow p), (p \leftarrow |L_p|).
L5 If (p = \Lambda) or (K_p > K_q) go to L3.
    Otherwise set (s \leftarrow p), (p \leftarrow |L_p|) and go to L5.

L6 Set (|L_s| \leftarrow q), (s \leftarrow q), (q \leftarrow |L_q|).
L7 If (q = \Lambda) or (K_q \le K_p) go to L3.
    Otherwise set (s \leftarrow q), (q \leftarrow |L_q|) and go to L7.

Explanation.
In L4 we link the current output tail (s) to the head of the next run from the (p)-list. Step L5 then advances (s) and (p) along that run without resetting (|L_s|), because the nodes are already linked: after L4 we have (|L_s| = p), and each iteration of L5 preserves this invariant. When the condition (K_p \le K_q) fails (or the (p)-list is exhausted), we return to L3, which will now branch to L6. L6 then performs the single necessary link change, connecting the last node of the (p)-run to the head of the (q)-run. The symmetric reasoning applies to L6-L7.

Verification.
Consider merging (p)-list (1 \to 3 \to 5) and (q)-list (2 \to 4 \to 6). Initially (s) points to a dummy header.

  • L3: (1 \le 2) → L4.
  • L4: (|L_s| \leftarrow 1), (s \leftarrow 1), (p \leftarrow 3).
  • L5: (p=3), (K_p=3 > 2) → L3.
  • L3: (3 > 2) → L6.
  • L6: (|L_s| \leftarrow 2) (changes link of 1 from 3 to 2), (s \leftarrow 2), (q \leftarrow 4).
  • L7: (q=4), (K_q=4 > 3) → L3.
  • L3: (3 \le 4) → L4.
  • L4: (|L_s| \leftarrow 3) (changes link of 2 from 4 to 3), (s \leftarrow 3), (p \leftarrow 5).
  • L5: (p=5), (K_p=5 > 4) → L3.
    … and so on. The output list becomes (1 \to 2 \to 3 \to 4 \to 5 \to 6) with exactly one link assignment per run. No redundant stores occur.

The modification reduces the number of link assignments from one per element to one per run, cutting them roughly in half on random data. The inner loops L5 and L7 are simple pointer advances and can be coded very efficiently in MIX (or any machine language). This completes the proof. ∎