TAOCP 5.2.1 Exercise 2
Let step S4 in Algorithm S be the comparison step that determines whether the current key $K$ should be inserted before $K_i$ or whether $K_i$ should be moved right.
Section 5.2.1: Sorting by Insertion
Exercise 2. [**] [11] Would Algorithm S still sort numbers correctly if the relation “kK > Kk,” in step S3 were replaced by “Kk > k;”?
Verified: yes
Solve time: 1m15s
Let step S4 in Algorithm S be the comparison step that determines whether the current key $K$ should be inserted before $K_i$ or whether $K_i$ should be moved right. The original condition enforces the invariant that after processing position $j$, the sequence $K_1,\dots,K_j$ is nondecreasing.
If the comparison in step S3 is replaced by its reversal, then every decision that previously preserved $K_i \le K$ is replaced by a decision that preserves $K_i \ge K$. The movement logic in steps S4–S5 is unchanged, so elements larger than the current key are no longer shifted right; instead, elements smaller than the current key are shifted right.
Consequently, after the $j$th pass, the processed portion satisfies $K_1 \ge K_2 \ge \cdots \ge K_j$. The loop structure and termination condition remain valid, so every element is still inserted into its correct position with respect to this reversed ordering. After completion, the entire file is arranged in nonincreasing order.
Since the specification of Algorithm S requires $K_1 \le \cdots \le K_N$, the modified algorithm does not meet the stated sorting requirement, although it still produces a correctly ordered sequence in the opposite sense. This completes the analysis. ∎