 Counting Sort can be insanely fast - faster than . It only works on integers, or other discrete things. Here's how it works: 1. Loop through the array, counting the number of times each integer appears. Also keep track of the the smallest and biggest integers in the array. This takes time. 2. Iterate from the smallest integer to the biggest integer, adding each value the corrent number of times. This takes time. Here's the code: answer tc sc 

Counting Sort

-----problem-----



Counting Sort can be insanely fast - faster than $O(n \log n)$. 
It only works on integers, or other discrete things.

-----solution-----

Here's how it works:

\split{{

1. Loop through the array, counting the number of times each integer appears. Also keep track of the the smallest and biggest integers in the array. This takes $O(n)$ time. 

2. Iterate from the smallest integer to the biggest integer, adding each value the corrent number of times. This takes $O(\texttt{maxval - minval})$ time.

}}


Here's the code:



\answer

\tc $O(n + \texttt{maxval - minval})$

\sc $O(n)$

Iteration

Counting Sort