Where counting sort places a value
Counting sort is run on the array whose values lie in . After tallying how many times each value occurs, the algorithm takes a prefix sum of those tallies to decide where each value's block begins in the sorted output, then writes elements into a -indexed output array. At which -indexed position does the first (leftmost) get placed?
Show hints (2)+
- First tally each value's count, then prefix-sum: a value's block starts at the cumulative count of all smaller values.
- The block for starts at .
Answer
Reveal answer →Final answer
3
Want the full step-by-step worked solution? It's part of Premium — along with a worked solution for every question in the bank.