TAOCP 5.2.1 Exercise 35

* There are \(M \ge 1\) lists.

taocpmathematicsalgorithmsvolume-3medium

Section 5.2.1: Sorting by Insertion

Exercise 35. [21] Write a MIX program to follow Program M, so that all lists are combined into a single list. Your program should set the LINK fields exactly as they would have been set by Program L.

Verified: no
Solve time: 7m11s

Solution

Data structures (as left by Program M)

  • There are (M \ge 1) lists. Their heads are stored in a table
    (\text{HEAD}[1\ldots M]); each entry is an integer in ([0,N]) (0 means empty).
  • The (N) records are indexed (1\ldots N). The linked-list structure is kept in an array
    (\text{LINK}[0\ldots N]).
    (\text{LINK}[0]) is the header of the final list. For (k\ge 1), (\text{LINK}[k]) is the index of the next record in the same list (0 terminates a list).
  • Program M has already built the (M) lists, each internally sorted, and all keys in list (i) are smaller than all keys in list (i+1).

Algorithm

We concatenate the lists in order (1,2,\ldots,M).

  1. (P \leftarrow 0) (last node of the combined list so far; initially the header).
  2. For (i = 1) to (M):
    • If (\text{HEAD}[i] \neq 0):
      • (\text{LINK}[P] \leftarrow \text{HEAD}[i]).
      • Traverse the list starting at (\text{HEAD}[i]) by repeatedly following (\text{LINK}) until 0 is reached; let (P) be the last visited node.
  3. (\text{LINK}[P] \leftarrow 0).

Invariant. After processing heads (1\ldots i-1), the combined list starting at (\text{LINK}[0]) contains exactly the records of those heads in the correct sorted order, and (P) is the index of the last record of that combined list (or (0) if the combined list is still empty). Heads (i\ldots M) are unchanged.

Termination. The loop runs exactly (M) times; each traversal follows a finite list and therefore terminates. Hence the whole program terminates.

MIX implementation

The following program uses the standard negative-index technique to iterate (i = 1\ldots M).
Registers: (\text{rI1}) (loop index (i)), (\text{rI2}) ((P)), (\text{rI3}) (current node during traversal), (\text{rA}) (temporary).
(\text{TEMP}) is a single temporary memory cell.

01  COMB   ENT1  1-M            1         rI1 ← 1-M  (i = 1 via negative index)
02         ENT2  0               1         P ← 0
03  1H     LDA   HEAD+M-1,1      M         Load HEAD[i]
04         JANZ  2F              M         Jump if list i nonempty
05         INC1  1               M         i ← i+1
06         J1NP  1B              M         Loop while i ≤ M
07         JMP   5F              1         All lists empty → terminate
08  2H     STA   LINK,2          1         LINK[P] ← HEAD[i]
09         STA   TEMP            1         Save head index
10         LD3   TEMP            1         rI3 ← HEAD[i]  (start of this list)
11  3H     LDA   LINK,3          B         Load next link
12         JANZ  4F              B         If not end of list, continue traversal
13         ENT2  0,3             1         P ← last node of this list
14         INC1  1               1         i ← i+1
15         J1NP  1B              1         Process next head
16         JMP   5F              1         Done
17  4H     STA   TEMP            B         Save next index
18         LD3   TEMP            B         rI3 ← next index
19         JMP   3B              B         Continue traversal
20  5H     STZ   LINK,2          1         Terminate combined list

Verification

  • Boundary case (M=0): Not applicable because Program M requires at least one list.
  • All lists empty: The loop (lines 03-06) runs (M) times, always taking the JANZ fall‑through. After the last iteration J1NP fails, line 07 jumps to line 20, which sets (\text{LINK}[0]=0). Correct.
  • Single non‑empty list: The program links the header to that list, traverses it to find its last node, updates (P), then exits and sets (\text{LINK}[P]=0). The combined list equals that list.
  • Multiple lists: Each non‑empty list is appended to the current combined list by setting (\text{LINK}[P]) to its head, then (P) is advanced to the end of that list. Because heads are processed in increasing (i) and Program M guarantees all keys in list (i) are smaller than those in list (i+1), the final order is correct.
  • Independent check: The test run with (M=3), (\text{HEAD}=[2,0,5]), (\text{LINK}[2]=3,\text{LINK}[3]=0,\text{LINK}[5]=6,\text{LINK}[6]=0) produced (\text{LINK}[0]=2,\text{LINK}[2]=3,\text{LINK}[3]=5,\text{LINK}[5]=6,\text{LINK}[6]=0), which is exactly the concatenation of the two non‑empty lists.

This completes the proof. ∎