TAOCP 5.2 Exercise 3
No.
Exercise 3. [**] [21] Would Algorithm C still work properly if the test in step C4 were changed from “$K_i < K_j$” to “$K_i \leq K_j$”?
Verified: yes
Solve time: 5m44s
No. The modified algorithm still assigns exactly one unit to one of the two counters for every pair $(i,j)$ with $j<i$, but the tie-breaking rule is reversed.
With the original test, when $K_i=K_j$ and $j<i$, the condition $K_i<K_j$ is false, so COUNT[i] is increased. Hence among equal keys, the later record receives the larger count and therefore appears after the earlier record. Exercise 2 shows that this yields a correct ordering.
If the test is changed to $K_i\le K_j$, then for $K_i=K_j$ and $j<i$, COUNT[j] is increased instead. Thus the earlier record receives the larger count and appears after the later record. For equal keys, the records are therefore placed in the reverse of their original order.
The resulting counts are still distinct. For any pair of equal keys, exactly one of the corresponding counts is increased, so no two equal keys receive the same final position. For unequal keys, the same record receives the increment as before. Consequently COUNT[i]+1 still gives the rank of $R_i$ in a nondecreasing ordering of the keys, but equal keys appear in reverse order of their indices. Therefore Algorithm C still sorts correctly, although it is no longer stable in the sense of Exercise 2. $\boxed{\text{Yes}}$