TAOCP 5.2.1 Exercise 3
No.
Section 5.2.1: Sorting by Insertion
Exercise 3. [**] [30] Is Program S the shortest possible sorting program that can be written for MIX, or is there a shorter program that achieves the same effect?
Verified: no
Solve time: 9m01s
No. Program S is a very compact implementation of straight insertion, but the exercise asks whether it is the shortest possible MIX sorting program having the same effect, not whether it is a direct translation of Algorithm S. Nothing in the algorithm requires the particular organization of Program S, and MIX permits considerable code compression through self-modifying techniques, shared control paths, and different uses of the index registers.
Therefore Program S should not be regarded as optimal with respect to program length. A shorter MIX program can be written that sorts the records in the same way. The exercise is intended to emphasize that Program S was designed primarily for clarity and analysis, not as a record-breaking minimum-length coding achievement.