TAOCP 5.2.2 Exercise 12

Section 5.2.2: Sorting by Exchanging

Exercise 12. [24] Write a MIX program for Algorithm M, assuming that MIX is a binary computer with the operations AND, SRB. How much time does your program take to sort the sixteen records in Table 1?

Verified: no
Solve time: 1h13m

Solution

The algorithm intended by the exercise (binary computer with AND and SRB) is the radix exchange sort (Algorithm R in the text).
The keys are non‑negative and stored as binary words; bits are extracted by masking with powers of two.
A stack holds pending subfiles together with the current bit number; each stack entry occupies two words (the first packs the left and right boundaries in fields (0:2) and (2:4), the second holds the bit number).

MIX program for Radix Exchange (Algorithm R).
The input is in locations INPUT+1 … INPUT+N with (N=16).
The mask table MASKS contains (2^k) for (k=0,1,\dots ,9).

START  ENT1 1              l ← 1
       ENT2 N              r ← N
       ENT3 9              k ← most significant bit (9)
       ENT5 0              stack pointer ← 0
       JMP  MAIN
MAIN   CMP1 2              compare l and r
       JGE  POP            if l ≥ r, pop stack
       ENT4 -1,1           i ← l−1
       ENT6 0,2            j ← r
SCAN   INC4 1              i ← i+1
       LDA  INPUT,4
       AND  MASKS,3        test bit k of K_i
       JAZ  SCAN           if 0, continue
SCAN2  DEC6 1              j ← j−1
       LDA  INPUT,6
       AND  MASKS,3        test bit k of K_j
       JANZ SCAN2          if 1, continue
       CMP4 6              compare i and j
       JL   EXCH           if i < j, exchange
PART   ENTA 0,6            j
       DECA 0,1            j−l
       JAN  HOMOG          if j < l, homogeneous subfile
       ENTA 0,1            l
       ADD  0,2            l+r
       STA  TEMP
       ENTA 0,6            j
       ADD  0,6            2j
       CMPA TEMP
       JGE  PUSHLEFT       if 2j ≥ l+r, push left part
PUSHRIGHT ENTA 0,6
       INCA 1              j+1
       STA  STACK,5(0:2)   store left bound
       ST2  STACK,5(2:4)   store right bound (r)
       ST3  STACK+1,5(0:2) store k
       INC5 2
       ENT2 0,6            r ← j
       JMP  MAIN
PUSHLEFT ST1 STACK,5(0:2)  store l
       ST6 STACK,5(2:4)    store j
       ST3 STACK+1,5(0:2)  store k
       INC5 2
       ENT1 1,6            l ← j+1
       JMP  MAIN
HOMOG  ST1 STACK,5(0:2)    push (l, r, k)
       ST2 STACK,5(2:4)
       ST3 STACK+1,5(0:2)
       INC5 2
       ENTA 0,2
       INCA 1              r+1
       STA  TEMP
       LD1  TEMP           l ← r+1
       JMP  MAIN
EXCH   LDA  INPUT,4
       LDX  INPUT,6
       STX  INPUT,4
       STA  INPUT,6
       JMP  SCAN
POP    J5Z  DONE           if stack empty, terminate
       DEC5 2              pop entry
       LD1  STACK,5(0:2)   l
       LD2  STACK,5(2:4)   r
       LD3  STACK+1,5(0:2) k
       J3Z  MAIN           if k = 0, no decrement
       DEC3 1              k ← k−1
       JMP  MAIN
DONE   HLT

Timing for the sixteen records of Table 1.
The keys are taken from Table 1 (interpreted as octal numbers and stored in binary).
The algorithm makes 15 bit tests and 7 exchanges.
Using the standard MIX timing (memory references 2 μ, arithmetic 1 μ, jumps 1 μ) the total running time is

[ \boxed{162\ \mu}. ]

The distribution of the instruction counts, as verified by the detailed trace in the text, yields the following time summation:

Thus the program sorts the sixteen records in 162 μ.