TAOCP 5.2 Exercise 2
For each pair $(j,i)$ with $j<i$, step C4 increases exactly one of `COUNT[j]` or `COUNT[i]`.
Exercise 2. [**] [21] Show that Algorithm C works properly when equal keys are present. If $K_i = K_j$ and $j < i$, does $R_i$ come before or after $R_j$ in the final ordering?
Verified: no
Solve time: 10m13s
For each pair $(j,i)$ with $j<i$, step C4 increases exactly one of COUNT[j] or COUNT[i]. If $K_i<K_j$, then COUNT[j] is increased; otherwise COUNT[i] is increased. Hence, after all comparisons have been made, COUNT[i] equals the number of indices $j\ne i$ for which either $K_j<K_i$, or $K_j=K_i$ and $j<i$. Therefore COUNT[i] is precisely the number of records that must precede $R_i$ in the ordering obtained by sorting first by key and, among equal keys, by increasing index. Consequently the values COUNT[i]+1 are all distinct and give the correct final positions of the records.
If $K_i=K_j$ and $j<i$, the comparison of this pair occurs when step C4 is applied to $(j,i)$. Since $K_i<K_j$ is false, COUNT[i] is increased. Thus $R_i$ receives one more count than $R_j$ from their mutual comparison. Every record with key equal to $K_i=K_j$ and index less than $i$ contributes to COUNT[i], while records with larger indices do not. Hence $R_j$ is assigned a smaller final position than $R_i$. Therefore, when equal keys are present, the earlier record comes first: if $K_i=K_j$ and $j<i$, then $R_i$ comes after $R_j$ in the final ordering. $\boxed{\text{Algorithm C is stable; equal keys remain in their original order.}}$