TAOCP 5.2.1 Exercise 10
In step D3, Program D performs three actions before any comparison outcome is known: it sets $i = j - h$, it loads $K = K_j$, and it loads $R = R_j$.
Section 5.2.1: Sorting by Insertion
Exercise 10. [22] [22] If $K_i > K_j$, when we begin step D3, Algorithm D specifies a lot of actions that accomplish nothing. Show how to modify Program D so that this redundant computation can be avoided, and discuss the merits of such a modification.
Verified: yes
Solve time: 1m29s
Solution
In step D3, Program D performs three actions before any comparison outcome is known: it sets $i = j - h$, it loads $K = K_j$, and it loads $R = R_j$. When the condition $K_i > K_j$ holds at the start of D3, the execution immediately proceeds to repeated executions of D5, during which records $R_i$ are shifted rightward by one increment $h$ until the correct position for $R_j$ is found. In this situation, the early evaluation and storage of $R_j$ and the initialization of the working copy $R$ do not contribute to any decision process, since no insertion position has yet been determined and no use of $R_j$ occurs until step D6.
To remove this redundancy, the assignment of $R_j$ is delayed until the final insertion point is known, and the comparison loop is executed using only the key value $K_j$. The modified structure separates the search phase from the insertion phase.
Step D3 is replaced by a single initialization of the index and key:
D3′. Set $i = j - h$ and $K = K_j$.
Step D4 remains unchanged:
D4. If $K \ge K_i$, go to D6.
Step D5 remains unchanged:
D5. Set $R_{i+h} = R_i$, then $i = i - h$. If $i \ge 0$, go back to D4.
The insertion step is modified so that the element is written only once the correct location has been determined:
D6′. Set $R_{i+h} = R_j$.
This modification eliminates all premature handling of $R_j$ in the unsuccessful cases $K_i > K_j$, since in those cases control cycles through D5 without ever requiring access to $R_j$. The value $K_j$ alone governs all comparisons, and no auxiliary storage of the record is needed during the search phase.
A further refinement removes the need to treat $R_j$ as a separately loaded object at all during the shifting phase. Since the algorithm already stores $R_j$ in its original position until D6′, no data movement is required until the final assignment. This reduces the number of register loads and store operations associated with unsuccessful comparisons, while preserving the correctness of the insertion process.
The resulting program performs the same sequence of comparisons and the same sequence of shifts $R_i \leftarrow R_{i+h}$, but avoids redundant loading and holding of $R_j$ in the inner loop. The asymptotic behavior remains unchanged, since the number of comparisons and moves is governed by the same inversion structure as in Program D, but the constant factors in execution time are reduced by eliminating unnecessary data movement in cases where $K_i > K_j$.
This completes the proof. ∎