Exercise 8.2.2

Prove that COUNTING-SORT is stable.

An informal argument will suffice.

Let's say that two elements at indices $i_1 < i_2$ are equal to each other. In the sorted array, they take place at indices $j_1 + 1 = j_2$. Since the COUNTING-SORT processes the input array in reverse order, $A[i_2]$ is put in $B[j_2]$ first and then $A[i_1]$ is put in $A[j_2]$. Since the two elements preserve their order, the algorithm is stable.