Where counting sort places a value

Counting sort is run on the array [3, 1, 3, 2, 1, 3, 0][\,3,\ 1,\ 3,\ 2,\ 1,\ 3,\ 0\,] whose values lie in {0,1,2,3}\{0,1,2,3\}. 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 00-indexed output array. At which 00-indexed position does the first (leftmost) 22 get placed?

Show hints (2)+
  1. First tally each value's count, then prefix-sum: a value's block starts at the cumulative count of all smaller values.
  2. The block for 22 starts at count[0]+count[1]\text{count}[0]+\text{count}[1].

Answer

Reveal 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.

Asked at: Citadel, Two Sigma

Related questions