Prove that \(\textsc{Counting-Sort}\) is stable.
A sorting algorithm is stable if elements with equal values appear in the output in the same relative order as they appeared in the input. We now prove that counting sort has this property.
Consider two elements \(A[i]\) and \(A[j]\) where \(i < j\) (so \(A[i]\) appears before \(A[j]\) in the input) and \(A[i] = A[j] = v\) for some value \(v\).
The key to the proof is understanding what happens in the final loop (lines 10-12), which processes elements from right to left.
After lines 7-8, \(C[v]\) contains the total count of elements with values less than or equal to \(v\). This tells us the final position range for all elements equal to \(v\).
Since the loop processes elements from \(A[n]\) down to \(A[1]\):
- Element \(A[j]\) is encountered first (remember \(j > i\))
- When we process \(A[j] = v\), we place it at position \(C[v]\) in the output array \(B\)
- We then decrement \(C[v]\) (line 12)
- Later, when we process \(A[i] = v\), it gets placed at the new value of \(C[v]\), which is one position to the left of where \(A[j]\) was placed
Since \(A[j]\) appears later in the input but is processed first in the backward loop, it goes into a higher index position in \(B\). Then \(A[i]\) goes into a lower index position. This means \(A[i]\) appears before \(A[j]\) in the sorted output, preserving their relative order from the input.
This holds for any pair of equal elements, proving that counting sort is stable.