TAOCP 5.2.4 Exercise 9

**Register assignment** rI1 = i (left source pointer) rI2 = j (right source pointer) rI3 = k (destination pointer) rI5 = q (elements left in current left run) rI6 = r (elements left in current right r...

taocpmathematicsalgorithmsvolume-3medium

Section 5.2.4: Sorting by Merging

Exercise 9. [24] Write a MIX program for Algorithm S. Specify the instruction frequencies in terms of quantities analogous to $A, B', B'', C', \ldots$ in Program L.

Verified: no
Solve time: 12m38s

Solution

MIX Program for Algorithm S (Straight Two-Way Merge Sort)

Register assignment
rI1 = i (left source pointer)
rI2 = j (right source pointer)
rI3 = k (destination pointer)
rI5 = q (elements left in current left run)
rI6 = r (elements left in current right run)
rA, rX = key comparison and data movement

Memory locations
N - number of records (given)
S - source area flag (0 or 1)
P - current run length p
L_PTR - destination boundary l
TEMP - temporary storage
INCK - self‑modifying instruction (holds INC3 or DEC3)
INC3W, DEC3W - instruction words for INC3 and DEC3

Areas
AREA1 = 1 … N, AREA2 = N+1 … 2N

01 START   LDA =0=           (1)
02         STA S             (1)
03         LDA =1=           (1)
04         STA P             (1)
05         JMP PASS          (1)
06 PASS    LDA S             (A)
07         JANZ S1SET        (A)
08 S0SET   ENT1 1            (I)
09         ENT2 N            (I)
10         ENT3 N            (I)
11         LDA =2*N+1=       (I)
12         STA L_PTR         (I)
13         JMP DIRINI        (I)
14 S1SET   ENT1 N+1          (J)
15         ENT2 2*N          (J)
16         ENT3 0            (J)
17         LDA =N+1=         (J)
18         STA L_PTR         (J)
19 DIRINI  LDA INC3W         (A)
20         STA INCK          (A)
21         LD5 P             (A)
22         LD6 P             (A)
23         JMP S3            (A)
24 S3      LDA 0,1           (C)
25         CMPA 0,2          (C)
26         JG S8             (C)
27 S4      INCK              (C1)
28         LDA 0,1           (C1)
29         STA 0,3           (C1)
30         INC1 1            (C1)
31         DEC5 1            (C1)
32         J5P S3            (C1)
33         JMP S6            (B_L)
34 S6      INCK              (F)
35         CMP3 L_PTR        (F)
36         JE S13            (G)
37         LDA 0,2           (F)
38         STA 0,3           (F)
39         DEC2 1            (F)
40         DEC6 1            (F)
41         J6P S6            (F - B_L)
42         JMP S12           (B_L - G)
43 S8      INCK              (C2)
44         LDA 0,2           (C2)
45         STA 0,3           (C2)
46         DEC2 1            (C2)
47         DEC6 1            (C2)
48         J6P S3            (C2 - B_R)
49         JMP S10           (B_R)
50 S10     INCK              (F')
51         CMP3 L_PTR        (F')
52         JE S13            (G')
53         LDA 0,1           (F')
54         STA 0,3           (F')
55         INC1 1            (F')
56         DEC5 1            (F')
57         J5P S10           (F' - B_R)
58         JMP S12           (B_R - G')
59 S12     LDA INCK          (H)
60         CMPA INC3W        (H)
61         JE SETDEC         (H1)
62         LDA INC3W         (H2)
63         STA INCK          (H2)
64         JMP SWAPKL        (H)
65 SETDEC  LDA DEC3W         (H2)
66         STA INCK          (H2)
67 SWAPKL  ST3 TEMP          (H)
68         LD3 L_PTR         (H)
69         LDA TEMP          (H)
70         STA L_PTR         (H)
71         LD5 P             (H)
72         LD6 P             (H)
73         JMP S3            (H)
74 S13     LDA P             (A)
75         ADD P             (A)
76         STA P             (A)
77         CMPA N            (A)
78         JGE DONE          (A)
79         LDA S             (A)
80         XOR =1=           (A)
81         STA S             (A)
82         JMP PASS          (A)
83 DONE    LDA S             (1)
84         JANZ HALT         (1)
85         ENT1 N            (1)
86 COPY    LDA N,1           (K)
87         STA 0,1           (K)
88         DEC1 1            (K)
89         J1P COPY          (K)
90 HALT    HLT               (1)

Frequency Analysis

The following quantities characterize the execution. They are analogous to the variables A, B, C, … used in Program L (Section 5.2.1).

Symbol Meaning Value / Relation
A Number of passes A = ⌈log₂ N⌉
B Total number of merges (executions of S12) B = Σ_{k=0}^{A-1} ⌈N / 2^{k+1}⌉
C Total number of comparisons (executions of S3) Data‑dependent
C1 Number of times left key ≤ right key in main loop C1 = executions of S4
C2 Number of times left key > right key in main loop C2 = C - C1 = executions of S8
D Total records moved D = N·A = C1 + C2 + F + F'
B_L Merges where left run exhausted first B_L = executions of JMP S6 (line 33)
B_R Merges where right run exhausted first B_R = B - B_L = executions of JMP S10 (line 49)
F Executions of first drain loop (S6) Data‑dependent
F' Executions of second drain loop (S10) Data‑dependent
G End‑of‑pass detections in S6 (JE S13 taken) G ≤ A
G' End‑of‑pass detections in S10 (JE S13 taken) G' = A - G
H Executions of S12 body H = B
H1 Times INCK = INC3 at S12 H1 = ⌈H/2⌉
H2 Times INCK = DEC3 at S12 H2 = ⌊H/2⌋
I Passes with S = 0 I = ⌈A/2⌉
J Passes with S = 1 J = ⌊A/2⌋
K Executions of the final copy loop K = N if A odd, else 0

The frequencies of the conditional jumps are expressed in terms of the above:

  • Line 32 (J5P S3): jumps C1 - B_L times, falls through B_L times.
  • Line 41 (J6P S6): jumps F - B_L times, falls through B_L - G times.
  • Line 36 (JE S13): taken G times.
  • Line 42 (JMP S12): executed B_L - G times.
  • Line 48 (J6P S3): jumps C2 - B_R times, falls through B_R times.
  • Line 57 (J5P S10): jumps F' - B_R times, falls through B_R - G' times.
  • Line 52 (JE S13): taken G' times.
  • Line 58 (JMP S12): executed B_R - G' times.
  • Line 61 (JE SETDEC): taken H1 times.
  • Lines 62-63 executed H2 times; lines 65-66 executed H2 times.

All other instructions have the constant frequencies shown in parentheses in the program listing.

This completes the proof. ∎