The Second Three
Counting sort over keys runs on
index: 0 1 2 3 4 5 6
A = [3, 1, 4, 1, 5, 3, 1]After tallying and prefix-summing, C[v] holds the number of elements with key at most v:
| v | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| C[v] | 0 | 3 | 3 | 5 | 6 | 7 |
The output loop is the stable one: for j from n-1 down to 0, place A[j] at B[C[A[j]] - 1] and then decrement C[A[j]]. Which index of B receives A[5], the second 3 in the input?
Sign in to answer questions and track your progress
Sign In