Using Figure 8.2 as a model, illustrate the operation of \(\textsc{Counting-Sort}\) on the array \(A = \langle 6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2 \rangle\).
We trace through the algorithm step by step. We have \(n = 11\) and \(k = 6\) (maximum value).
Initial state:
\[A = [6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2]\]After lines 2-3 (initialize \(C\) to zeros):
\[C = [0, 0, 0, 0, 0, 0, 0]\]After lines 4-5 (count occurrences):
Count how many times each value appears:
- 0 appears 2 times
- 1 appears 2 times
- 2 appears 2 times
- 3 appears 2 times
- 4 appears 1 time
- 5 appears 0 times
- 6 appears 2 times
After lines 7-8 (cumulative sum):
Each \(C[i]\) now contains the number of elements \(\leq i\):
\[C = [2, 4, 6, 8, 9, 9, 11]\]
Processing loop (lines 10-12) working backward through \(A\):
Process \(A[11] = 2\): \(B[C[2]] = B[6] = 2\), then \(C[2] = 5\)
Process \(A[10] = 3\): \(B[C[3]] = B[8] = 3\), then \(C[3] = 7\)
Process \(A[9] = 1\): \(B[C[1]] = B[4] = 1\), then \(C[1] = 3\)
Process \(A[8] = 6\): \(B[C[6]] = B[11] = 6\), then \(C[6] = 10\)
Process \(A[7] = 4\): \(B[C[4]] = B[9] = 4\), then \(C[4] = 8\)
Process \(A[6] = 3\): \(B[C[3]] = B[7] = 3\), then \(C[3] = 6\)
Process \(A[5] = 1\): \(B[C[1]] = B[3] = 1\), then \(C[1] = 2\)
Process \(A[4] = 0\): \(B[C[0]] = B[2] = 0\), then \(C[0] = 1\)
Process \(A[3] = 2\): \(B[C[2]] = B[5] = 2\), then \(C[2] = 4\)
Process \(A[2] = 0\): \(B[C[0]] = B[1] = 0\), then \(C[0] = 0\)
Process \(A[1] = 6\): \(B[C[6]] = B[10] = 6\), then \(C[6] = 9\)
Final sorted output:
\[B = [0, 0, 1, 1, 2, 2, 3, 3, 4, 6, 6]\]The array is now sorted! Notice how the algorithm is stable: the two 0’s, two 1’s, two 2’s, two 3’s, and two 6’s maintain their relative order from the input.