TAOCP 5.2.1 Exercise 33

We first recall Program L (list insertion sort) from Section 5.

taocpmathematicsalgorithmsvolume-3medium

Section 5.2.1: Sorting by Insertion

Exercise 33. [25] Find a way to improve on Program L so that its running time is dominated by $5B$ instead of $7B$, where $B$ is the number of inversions. Discuss corresponding improvements to Program S.

Verified: no
Solve time: 43m30s

Solution

We first recall Program L (list insertion sort) from Section 5.2.1. The list is maintained in descending order (largest first) with a header node L₀. Each node originally consists of two words: a KEY word and a LINK word. The inner loop for inserting a new record with key K (held in rA) is:

LOOP: LDX   LINK,1      (2)  // load link of current node → rI1 (address of next node)
      LDA   KEY,1       (2)  // load key of next node
      CMPA  K           (2)  // compare with new key
      JG    LOOP        (1)  // if current key > K, continue

Each iteration examines one node that is greater than K. The number of such nodes over the whole sort is exactly the number of inversions B. Hence the loop contributes 7B units to the running time.

Improvement to 5B

Change the node representation so that each node occupies two consecutive words:

  • Word 0 (KEY): the key is stored in the address field (bytes 3:5).
  • Word 1 (LINK): the link (address of the next node’s KEY word) is stored in the address field.

The header L₀ contains only a LINK word pointing to the first KEY word.
Keep the new key K in index register rI2 (loaded once per insertion).
Use index register rI1 to point to the current LINK word (initially L₀’s LINK word).

The inner loop then becomes:

LOOP: LDX   1,1         (2)  // load link from current LINK word → rI1 = next KEY word
      CMP2  0,1         (2)  // compare rI2 (K) with key in address field of that KEY word
      J2L   LOOP        (1)  // if K < current key (i.e., current key > K), continue

Timing: Each iteration executes LDX (2), CMP2 (2), J2L (1 taken) = 5 units. The loop runs exactly once per inversion (when current key > K), so the dominant term becomes 5B. The exit case (when K ≥ current key) also takes 5 units (J2L not taken) and occurs N times, contributing only to lower‑order terms.

Insertion: After the loop, rI1 points to the KEY word of the first node with key ≤ K. The new node is inserted by adjusting the link in the preceding LINK word (at address rI1−1). This takes O(1) time per insertion and does not affect the 5B term.

Verification:

  • The list is in descending order, so we continue while current key > K.
  • CMP2 compares rI2 (K) with the address field of the word at rI1. Since the key is in the address field, the comparison is correct.
  • LDX 1,1 loads the address field of the word at rI1+1, which is exactly the LINK word of the node whose KEY word is at rI1. Hence rI1 becomes the address of the next KEY word.
  • The initial setup places rI1 at L₀’s LINK word, so the first LDX fetches the first KEY word.
  • A sentinel node with key = −∞ (address field = 0) at the end guarantees termination when K is smaller than all keys.

Corresponding improvements to Program S (straight insertion)

Program S’s inner loop (per move) is

CMPA  INPUT,2   (2)
JGE   EXIT      (1)
LDX   INPUT,2   (2)
STX   INPUT+1,2 (2)
DEC2  1         (1)
J2P   LOOP      (1)

totaling 9 units per inversion (9B). The same idea of keeping the inserted key in an index register and storing keys in address fields allows the comparison to be done with CMP1 (2 units) instead of CMPA, but the move operations (LDX/STX) still cost 4 units and the loop control (DEC2/J2P or a JMP) costs at least 2 units. Using a sentinel K₀ = −∞ at the beginning of the array eliminates the need for the J2P instruction (the comparison with the sentinel replaces it), saving 1 unit and reducing the coefficient from 9 to 8. However, the fundamental limitation is that records must be physically moved; the 5B achieved by Program L is possible only because list insertion avoids data movement entirely. Thus the most significant “corresponding improvement” is to use list insertion (Program L) instead of straight insertion when the records are large or when the constant factor matters.

This completes the proof. ∎