Suppose that we were to rewrite the for loop header in line 10 of the \(\textsc{Counting-Sort}\) as
$$\begin{aligned} 10& \quad \textbf{for }\,j\,=\,1\textbf{ to }\,A.length \\ \end{aligned}$$Show that the algorithm still works properly. Is the modified algorithm stable?
We analyze what happens when we change the iteration direction from backward to forward.
A.
Yes, the modified algorithm still correctly sorts the array. Here’s why:
When we process element \(A[j]\) with value \(v\):
- We look up \(C[v]\), which tells us how many elements are \(\leq v\)
- We place \(A[j]\) at position \(C[v]\) in array \(B\)
- We decrement \(C[v]\) to prepare for the next element with value \(v\)
This logic works regardless of whether we iterate forward or backward. The cumulative counts in \(C\) ensure that each value goes to a correct position in the sorted range. After all elements with value \(v\) are placed, they occupy positions \((C[v] + 1)\) through \((C[v] + \text{count of } v)\), which is correct.
B.
No, the modified algorithm is not stable. Here is a counterexample.
Consider \(A = [2_a, 2_b, 1]\) where subscripts distinguish equal elements.
After initializing and counting, \(C = [0, 1, 3]\) (after cumulative sum).
Processing forward (modified version):
- \(j = 1\): \(A[1] = 2_a\), so \(B[C[2]] = B[3] = 2_a\), then \(C[2] = 2\)
- \(j = 2\): \(A[2] = 2_b\), so \(B[C[2]] = B[2] = 2_b\), then \(C[2] = 1\)
- \(j = 3\): \(A[3] = 1\), so \(B[C[1]] = B[1] = 1\), then \(C[1] = 0\)
Result: \(B = [1, 2_b, 2_a]\)
Notice that \(2_b\) comes before \(2_a\) in the output, even though \(2_a\) came first in the input. The relative order is reversed!
Processing backward (original version) would give \(B = [1, 2_a, 2_b]\), preserving the original order.
The forward iteration places the first occurrence of each value at the highest available position and works downward, effectively reversing the order of equal elements.