TAOCP 5.5 Exercise 2
Table 1 gives the following MIX running-time estimates for list-sorting methods: \begin{aligned} \text{List insertion:} \qquad &1.
Section 5.5: Summary, History, and Bibliography
Exercise 2. [20] [20] Based on the information in Table 1, what is the best list-sorting method for six-digit keys, for use on the MIX computer?
Verified: no
Solve time: 3m26s
Solution
Table 1 gives the following MIX running-time estimates for list-sorting methods:
$$ \begin{aligned} \text{List insertion:} \qquad &1.25N^2+13.25N,\[2mm] \text{Multiple list insertion:} \qquad &0.175N^2+18N,\[2mm] \text{List merge:} \qquad &14.43N\ln N+4.92N,\[2mm] \text{Radix list sort:} \qquad &32N+4838. \end{aligned} $$
Since the keys have exactly six digits, the radix-list-sort formula is applicable. We compare it directly with each competitor.
Radix list sort versus list insertion
We have
$$ (1.25N^2+13.25N)-(32N+4838) =1.25N^2-18.75N-4838. $$
The positive root of
$$ 1.25N^2-18.75N-4838=0 $$
is approximately
$$ N\approx 69.7. $$
Hence for $N\ge 70$,
$$ 32N+4838 < 1.25N^2+13.25N. $$
Thus radix list sort is better than list insertion except for very small lists.
Radix list sort versus multiple list insertion
Similarly,
$$ (0.175N^2+18N)-(32N+4838) =0.175N^2-14N-4838. $$
The positive root of
$$ 0.175N^2-14N-4838=0 $$
is approximately
$$ N\approx 209.3. $$
Hence for $N\ge 210$,
$$ 32N+4838 < 0.175N^2+18N. $$
Again, radix list sort wins once $N$ is moderately large.
Radix list sort versus list merge
We compare
$$ 32N+4838 $$
with
$$ 14.43N\ln N+4.92N. $$
The crossover point satisfies
$$ 14.43N\ln N-27.08N-4838=0. $$
Evaluating:
$$ N=100: \qquad 14.43(100)\ln 100+4.92(100) \approx 7138, $$
while
$$ 32(100)+4838=8038. $$
Thus merge is slightly better at $N=100$.
For $N=200$,
$$ 14.43(200)\ln 200+4.92(200) \approx 16260, $$
while
$$ 32(200)+4838=11238. $$
Thus radix list sort is already better at $N=200$.
Therefore the crossover occurs between $100$ and $200$, roughly near $N\approx130$.
Conclusion
The only serious competitor is list merge. According to the formulas in Table 1, radix list sort becomes faster than list merge for lists of only moderate size, and it is also faster than both insertion methods once $N$ exceeds relatively small crossover values.
Because six-digit keys allow radix sorting with a fixed number of passes, its estimated MIX running time is
$$ 32N+4838, $$
which grows linearly with $N$ and eventually dominates all competing list-sorting methods in Table 1.
Hence the best list-sorting method for six-digit keys on the MIX computer is
$$ \boxed{\text{Radix list sort}.} $$