Use the count sort algorithm to write a function that receives a StaticArray and returns a

new StaticArray with the same content sorted in non$-$ascending order. The original array

must not be modified.

You may assume that the input array will contain at least one element, and that all elements

will be integers in the range $[-10$

$9$

$,10$

$9].$ It is guaranteed that the difference between the

maximum and minimum values in the input will be less than $1,000.$ You do not need to write

checks for these conditions.

Implement a solution that can sort at least $5,000,000$ elements in a reasonable amount of

time $($under a minute$).$ Note that using a traditional sorting algorithm $($even a fast sorting

algorithm like merge sort or shell sort$)$ will not pass the largest test case of $5,000,000$

elements.

For full credit, the function must be implemented with O$($n$+$k$)$ time complexity, where n is

the number of elements and k is the range of values.

Hint: The count sort algorithm $($also known as counting sort$)$ creates a sorted array by

counting the number of times each value appears in the unsorted array.

A possible first step would be to find the range of numbers in the array, and use that range

to create a new $$count array$$ that tabulates the number of times each element is present in

the original array. The $$count array$$ will then provide you with the information you need to

generate a sorted array.

Other functions in this assignment will help you determine how many different values could

be in the array, as well as the range of possible values present.

This problem may be challenging, but try to implement this algorithm yourself. For

further clarification on the count sort algorithm, here is some suggested reading: