TAOCP 5.2 Exercise 9

We assume the following memory layout and conventions, analogous to Program C: - `INPUT` is the base address of the input records; record \(R_j\) is stored in `INPUT+j` for \(1 \le j \le N\).

taocpmathematicsalgorithmsvolume-3hard

Section 5.2: Internal Sorting

Exercise 9. [29] Write a MIX program for Algorithm D, analogous to Program C and exercise 4. What is the execution time of your program, as a function of $N$ and $(v - u)$?

Verified: no
Solve time: 15m18s

Setup

We assume the following memory layout and conventions, analogous to Program C:

  • INPUT is the base address of the input records; record (R_j) is stored in INPUT+j for (1 \le j \le N).
  • OUTPUT is the base address of the output area; record (S_i) will be placed in OUTPUT+i.
  • COUNT is the address of COUNT[u]; hence COUNT[k] resides at COUNT + (k-u) for (u \le k \le v).
  • COUNT_BASE = COUNT - u; then COUNT[k] is at COUNT_BASE + k.
  • M = v - u (a non‑negative constant).
  • TEMP is a single temporary memory cell.
  • Registers:
    • rI1 - primary loop index (used for (j), (k), and the clearing index).
    • rI2 - holds the current key (K_j).
    • rI3 - holds the output index (i) during the distribution pass.
    • rA - accumulator for counts, keys, and records.
    • rX - holds a record during the move.

All instructions are assumed to take one unit of time.

Solution

MIX Program for Algorithm D

        D1. Clear COUNT[u..v].
01  START  ENT1  M            1
02   1H   STZ   COUNT,1      M+1
03         DEC1  1            M+1
04         J1NN  1B           M+1

        D2. Loop on j = N..1; increment COUNT[K_j].
05         ENT1  N            1
06   2H   LD2   INPUT,1      N
07         LDA   COUNT_BASE,2 N
08         INCA  1            N
09         STA   COUNT_BASE,2 N
10         DEC1  1            N
11         J1P   2B           N

        D4. Accumulate counts: for k = 1..M, COUNT[u+k] += COUNT[u+k-1].
12         ENT1  1            1
13         CMP1  =M=          1
14         JG    4F           1
15   3H   LDA   COUNT-1,1    M
16         ADD   COUNT,1      M
17         STA   COUNT,1      M
18         INC1  1            M
19         CMP1  =M=          M
20         JLE   3B           M

        D5. Loop on j = N..1; move records to output.
21   4H   ENT1  N            1
22   5H   LD2   INPUT,1      N
23         LDA   COUNT_BASE,2 N
24         STA   TEMP         N
25         LD3   TEMP         N
26         LDX   INPUT,1      N
27         STX   OUTPUT,3     N
28         DECA  1            N
29         STA   COUNT_BASE,2 N
30         DEC1  1            N
31         J1P   5B           N

Execution Time

Summing the frequencies from the program:

  • D1: (1 + 3(M+1) = 3M + 4)
  • D2: (1 + 6N)
  • D4: (3 + 6M = 6M + 3) (valid for all (M \ge 0))
  • D5: (1 + 10N)

Total time (T) in MIX units:

[ \boxed{T = 9(v-u) + 16N + 9} ]

Verification

We verify the program logic and the timing formula by independent reasoning.

Correctness of the Program

  1. D1 clears COUNT[u] … COUNT[v] by iterating rI1 from (M = v-u) down to (0). With COUNT as the base of COUNT[u], COUNT,1 accesses COUNT[u+rI1]. The J1NN loop executes exactly (M+1) times, covering all required cells.
  2. D2 scans the input records once. LD2 INPUT,1 loads (K_j) into rI2. Because COUNT_BASE = COUNT - u, the address COUNT_BASE,2 equals COUNT + (K_j - u) = COUNT[K_j]. The sequence LDA, INCA, STA increments that counter. The loop runs for (j = N, N-1, \dots, 1).
  3. D4 computes the prefix sums. The loop index rI1 runs from (1) to (M). For a given (k =) rI1:
    • COUNT-1,1 = COUNT[u+k-1]
    • COUNT,1 = COUNT[u+k] The instructions LDA, ADD, STA perform COUNT[u+k] ← COUNT[u+k] + COUNT[u+k-1]. The top test CMP1 =M= / JG skips the loop entirely when (M=0); otherwise it executes exactly (M) times.
  4. D5/D6 distributes the records. For each (j) from (N) down to (1):
    • LD2 INPUT,1 gets (K_j).
    • LDA COUNT_BASE,2 loads (i = \text{COUNT}[K_j]).
    • STA TEMP / LD3 TEMP transfers (i) to rI3.
    • LDX INPUT,1 loads the record (R_j) into rX.
    • STX OUTPUT,3 stores (R_j) into (S_i).
    • DECA 1 / STA COUNT_BASE,2 decrements the counter. This matches step D6 exactly, and the reverse order of (j) guarantees stability.

Timing Verification

We recount each block using the instruction frequencies marked in the program:

Block Instructions (frequency) Total
D1 ENT1 (1), STZ (M+1), DEC1 (M+1), J1NN (M+1) (3M+4)
D2 ENT1 (1), then per iteration: LD2, LDA, INCA, STA, DEC1, J1P (6N) (6N+1)
D4 ENT1 (1), CMP1 (1), JG (1), then M times: LDA, ADD, STA, INC1, CMP1, JLE (6M) (6M+3)
D5 ENT1 (1), then per iteration: LD2, LDA, STA, LD3, LDX, STX, DECA, STA, DEC1, J1P (10N) (10N+1)
Sum (9M + 16N + 9)

Substituting (M = v-u) gives the boxed formula.

Boundary Cases

  • (M = 0) (all keys equal): D1 clears the single cell COUNT[u] (4 units). D2 increments it (N) times. D4 executes only the three setup instructions (ENT1, CMP1, JG taken) and skips the loop. D5 distributes the (N) records to consecutive output positions. Total time = (16N + 9), which matches (9\cdot0 + 16N + 9).
  • (N = 1): D2 and D5 each execute their loops once; all addresses are valid. The program works correctly.

The independent verification of the loop structures and the instruction counts confirms the derived execution time. ∎