count$\_$sort$($arr: StaticArray$)->$ StaticArray:

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 $[-109,109].$ 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.