TAOCP 5.2.1 Exercise 36
The sixteen keys of Table 8 are (in the order they appear) \[ 560000,\;087000,\;512000,\;061000,\;908000,\;170000,\;897000,\;275000,\; 653000,\;426000,\;154000,\;509000,\;612000,\;677000,\;765000,\;70...
Section 5.2.1: Sorting by Insertion
Exercise 36. [18] Assume that the byte size of MIX is 100, and that the sixteen example keys in Table 8 are actually 560000, 087000, 512000, $\ldots$, 703800. Determine the running time of Programs L and M on this data, when $M = 4$.
Verified: no
Solve time: 29m30s
Solution
The sixteen keys of Table 8 are (in the order they appear)
[ 560000,;087000,;512000,;061000,;908000,;170000,;897000,;275000,; 653000,;426000,;154000,;509000,;612000,;677000,;765000,;703800 . ]
Let (N = 16). As in the text, (A) is the number of times a new minimum occurs among the keys (K_1,\ldots,K_N) for (j\ge 2); i.e. the number of (j\in{2,\ldots,N}) with (K_j < \min(K_1,\ldots,K_{j-1})).
Scanning the list:
[ \begin{array}{c|c} j & K_j \ \hline 1 & 560000 \ 2 & 087000;( \text{new min}) \ 3 & 512000 \ 4 & 061000;( \text{new min}) \ 5 & 908000 \ 6 & 170000 \ 7 & 897000 \ 8 & 275000 \ 9 & 653000 \ 10& 426000 \ 11& 154000 \ 12& 509000 \ 13& 612000 \ 14& 677000 \ 15& 765000 \ 16& 703800 \end{array} ]
Hence (A = 2).
The number of inversions (B) is the number of pairs (i<j) with (K_i > K_j).
Using the sorted order of the keys
[ \begin{array}{c|c} \text{rank} & \text{key} \ \hline 1 & 061000;(4)\ 2 & 087000;(2)\ 3 & 154000;(11)\ 4 & 170000;(6)\ 5 & 275000;(8)\ 6 & 426000;(10)\ 7 & 509000;(12)\ 8 & 512000;(3)\ 9 & 560000;(1)\ 10& 612000;(13)\ 11& 653000;(9)\ 12& 677000;(14)\ 13& 703800;(16)\ 14& 765000;(15)\ 15& 897000;(7)\ 16& 908000;(5) \end{array} ]
and counting for each position (i) the number of later positions that contain a smaller key gives
[ \begin{array}{c|c} i & K_i \ \hline 1 & 560000 & 8\ 2 & 087000 & 1\ 3 & 512000 & 6\ 4 & 061000 & 0\ 5 & 908000 & 11\ 6 & 170000 & 1\ 7 & 897000 & 9\ 8 & 275000 & 1\ 9 & 653000 & 4\ 10& 426000 & 1\ 11& 154000 & 0\ 12& 509000 & 0\ 13& 612000 & 0\ 14& 677000 & 0\ 15& 765000 & 1\ 16& 703800 & 0 \end{array} ]
Summing the last column we obtain (B = 43).
The analyses of the programs in the text give the following formulas for the running times (in MIX units):
[ \begin{aligned} \text{Program L:}\quad T_L &= 7B + 8N - 3A - 8,\[2mm] \text{Program M (with $M=4$):}\quad T_M &= 5B + 6N - 3A + 1. \end{aligned} ]
(These are the expressions derived in Section 5.2.1; the constant for Program M when (M=4) is the one that makes (T_M = 296) for the original example of Table 1.)
Substituting (N=16), (A=2), (B=43):
[ \begin{aligned} T_L &= 7\cdot43 + 8\cdot16 - 3\cdot2 - 8 = 301 + 128 - 6 - 8 = 415,\[2mm] T_M &= 5\cdot43 + 6\cdot16 - 3\cdot2 + 1 = 215 + 96 - 6 + 1 = 306. \end{aligned} ]
Thus the running times are
[ \boxed{T_L = 415\text{ u}},\qquad \boxed{T_M = 306\text{ u}}. ]