TAOCP 5.2 Exercise 4
After Program C has terminated, the value $\mathrm{COUNT}[i]+1$ is the final position of record $R_i$.
Exercise 4. [**] [16] Write a MIX program that “finishes” the sorting begun by Program C; your program should transfer the keys to locations OUTPUT+1 through OUTPUT+N, in ascending order. How much time does your program require?
Verified: no
Solve time: 10m07s
After Program C has terminated, the value $\mathrm{COUNT}[i]+1$ is the final position of record $R_i$. Therefore the sorting can be completed by scanning the records once and placing each key directly into its destination:
01 ENT1 1
02 1H LDX COUNT,1
03 INCX 1
04 LDA INPUT,1
05 STA OUTPUT,0(X)
06 INC1 1
07 CMP1 =N=
08 JLE 1B
09 HLT
For each $i$, lines 02-05 perform the assignment $$ \text{OUTPUT}+\mathrm{COUNT}[i]+1 \leftarrow \text{INPUT}+i, $$ which places $K_i$ in its sorted position. Since the values $\mathrm{COUNT}[i]+1$ are precisely the positions $1,\ldots,N$, each output location receives exactly one key, and the keys appear in ascending order.
The running time is obtained by counting instructions. The initialization (line 01) costs $1u$. For each of the $N$ iterations, lines 02-07 cost $2+1+2+2+1+1=9u$. The final successful test at line 08 costs $1u$, and the preceding $N-1$ jumps cost $2(N-1)u$. Hence the total time is
$$ 1+9N+2(N-1)+1
11N. $$
Therefore the finishing program requires
$$ \boxed{11N\text{ units}} $$
of time.