TAOCP 5.2 Exercise 11

After Algorithm C, the `COUNT` array satisfies `COUNT[j] =` number of keys strictly less than `K_j`; hence the final position of record `R_j` is `COUNT[j] + 1`.

taocpmathematicsalgorithmsvolume-3math-hard

Section 5.2: Internal Sorting

Exercise 11. [M27] Write a MIX program for the algorithm of exercise 10, and analyze its efficiency.

Verified: no
Solve time: 1h33m

Solution

After Algorithm C, the COUNT array satisfies COUNT[j] = number of keys strictly less than K_j; hence the final position of record R_j is COUNT[j] + 1.
Exercise 10 asks to rearrange the records into their final order in place, using only the COUNT array and a constant amount of extra memory. The method follows each cycle of the permutation
π(j) = COUNT[j] + 1. While traversing a cycle we keep one record in a register, move the next record into the vacated place, and set COUNT[j] to zero to mark the position as processed. Because π is a permutation of 1 … N, every element belongs to exactly one cycle; zero is a safe marker since all destinations are positive.

MIX Program

The program assumes the same memory layout as Program C:

  • Records R_1 … R_N are stored in INPUT+1 … INPUT+N (one word each).
  • COUNT[1] … COUNT[N] holds the counts after Algorithm C.
  • N is the number of records.
  • Two extra memory cells I_SAVE and TEMP are used.

Registers:

  • rI1 ≡ i , outer loop index (1 … N)
  • rI2 ≡ j , current position inside a cycle
  • rI3 ≡ k , destination π(j)
  • rA, rX , used for loading/storing records
        START  ENT1  N            1       i ← N  (prepare to add 1 to COUNT)
    1H   LDA   COUNT,1           N       load COUNT[i]
         INCA  1                 N       add 1
         STA   COUNT,1           N       store back (now final position)
         DEC1  1                 N
         J1P   1B                N       repeat for i = N … 1
         ENT1  1                 1       i ← 1  (start permutation pass)
    2H   LDA   COUNT,1           N       load COUNT[i]
         JAZ   4F                N       if zero, already processed
         ST1   I_SAVE            C       save start of cycle
         ENT2  0,1               C       j ← i
         LDX   INPUT,2           C       rX ← R_j  (temp record)
    3H   LD3   COUNT,2           N       k ← COUNT[j]  (destination)
         STZ   COUNT,2           N       mark COUNT[j] = 0
         CMP3  I_SAVE            N       k = i ?
         JE    5F                N       yes → cycle complete
         LDA   INPUT,3           N−C     rA ← R_k
         STX   INPUT,3           N−C     R_k ← temp
         STA   TEMP              N−C     save displaced record
         LDX   TEMP              N−C     temp ← displaced record
         ENT2  0,3               N−C     j ← k
         JMP   3B                N−C     continue cycle
    5H   STX   INPUT,3           C       store final temp into R_i
    4H   INC1  1                 N       i ← i+1
         CMP1  N                 N       i ≤ N ?
         JLE   2B                N       yes → next i
         HLT                     1

Timing Analysis

Let C be the number of cycles in the permutation π (including 1‑cycles).
The frequencies and standard MIX execution times (1 unit for ENT, INC, DEC, JMP, conditional jumps; 2 units for LDA, STA, LDX, STX, LDi, STi, STZ, CMPi) are:

Instruction Frequency Units
ENT1 N (start) 1 1
LDA COUNT,1 (increment pass) N 2
INCA 1 N 1
STA COUNT,1 N 2
DEC1 1 N 1
J1P 1B N 1
ENT1 1 1 1
LDA COUNT,1 (perm pass) N 2
JAZ 4F N 1
ST1 I_SAVE C 2
ENT2 0,1 C 1
LDX INPUT,2 C 2
LD3 COUNT,2 N 2
STZ COUNT,2 N 2
CMP3 I_SAVE N 2
JE 5F N 1
LDA INPUT,3 N−C 2
STX INPUT,3 (swap) N−C 2
STA TEMP N−C 2
LDX TEMP N−C 2
ENT2 0,3 N−C 1
JMP 3B N−C 1
STX INPUT,3 (cycle end) C 2
INC1 1 N 1
CMP1 N N 2
JLE 2B N 1
HLT 1 1

Summing the 1‑unit and 2‑unit instructions separately:

  • 1‑unit total =
    1 + N + N + N + 1 + N + C + N + (N−C) + (N−C) + N + N + 1
    = 9N − C + 3.

  • 2‑unit total =
    2(N + N + N + C + C + N + N + N + (N−C) + (N−C) + (N−C) + (N−C) + C + N)
    = 2(11N − C) = 22N − 2C.

Hence the overall running time for the rearrangement phase is

[ T = (9N - C + 3) + (22N - 2C) = 31N - 3C + 3 \quad \text{units}. ]

Extremes:

  • Minimum C = 1 (one cycle of length N):
    ( T_{\min} = 31N ).
  • Maximum C = N (identity permutation):
    ( T_{\max} = 28N + 3 ).

Average case: For a random permutation the expected number of cycles is the harmonic number H_N = \ln N + \gamma + O(1/N). Thus the average running time is

[ T_{\text{avg}} = 31N - 3\ln N + O(1). ]

Verification

For N = 1, C = 1 the program takes exactly 31 units, matching the formula.
The program correctly handles 1‑cycles (the JE branch is taken immediately) and destroys the COUNT array (all entries become zero), which is acceptable because the permutation is no longer needed after rearrangement.

Notes

  • If records occupy L > 1 words, the move instructions LDX INPUT,2, LDA INPUT,3, STX INPUT,3, and STX INPUT,3 (at 5H) must be repeated L times, increasing the (N−C) and C blocks accordingly. The cycle‑header and outer‑loop costs remain unchanged.
  • The program uses exactly two extra memory cells (I_SAVE and TEMP) and a few registers, satisfying the “no excess memory” requirement. ∎