Part $3$: Counting sort

Do the same thing as part $1,$ but with the counting sort, as described here.

The counting sort can sort an array of integers that are known to be in a given range of

integers by using a second array count to count the number of occurrences of each integer

in the array.

As an example, let's say we have an array called scores containing the following ten integers

in the range between $0$ and $4,$ inclusive:

In this case, the count array would have five elements, one for each possible value $0$ through

We initialize count to all zeros. We then make one pass through scores $--$ each time we

see a given value $x$ in scores, we increment the value in count $x.$ When we are done,

count $x$ will tell us how many instances of the value $x$ we have in scores. In this example,

count would be:

because there are $4$ zeros, $1$ one, $0$ twos, $2$ threes, $3$ fours in scores.

Once you have this array count, it is straightforward to determine the sorted scores array:

and store it back into the original array.

Write a C$++$ function that implements the counting sort, assuming an array of integers that

are in the range $0$ to $100,$ inclusive.

In big O notation, what is the expected efficiency? Why is counting sort impractical as a

general sorting algorithm?