TAOCP 5.2 Exercise 1
Algorithm C still works if $i$ varies from $2$ up to $N$ in step C2 instead of from $N$ down to $2$, because the comparisons made in step C4 depend only on the relative ordering of $K_i$ and $K_j$, no...
Exercise 1. [**] [15] Would Algorithm C still work if i varies from 2 up to N in step C2, instead of from N down to 2? What if j varies from 1 up to i − 1 in step C3?
Verified: no
Solve time: 10m42s
Algorithm C still works if $i$ varies from $2$ up to $N$ in step C2 instead of from $N$ down to $2$, because the comparisons made in step C4 depend only on the relative ordering of $K_i$ and $K_j$, not on the order in which $i$ is processed. Each pair $(i,j)$ with $1 \le j < i \le N$ is still compared exactly once, so COUNT[i] and COUNT[j] are updated correctly, and the final values of COUNT[i] + 1 correctly specify the final positions of the records. The loop direction of $i$ affects only the sequence in which counts are incremented, not the final counts themselves.
Similarly, if $j$ varies from $1$ up to $i-1$ in step C3, Algorithm C remains correct. Step C4 updates COUNT[i] or COUNT[j] based on the comparison, and each pair $(i,j)$ is still considered once. The cumulative effect on COUNT is independent of whether $j$ decreases from $i-1$ to $1$ or increases from $1$ to $i-1$, because increments are commutative. Therefore, both modifications preserve the correctness of the algorithm.
This completes the proof.
∎