Counting Sort

An examples of a Stable matching algorithms It counts how many duplicates of a number in an array

Antagelse: Vi vet hva det største tallet er

Telle array - Hvor mange ganger et tall forekommer Output - 1 forekomst av tallet 0, 1 forekomst av tallet 1, 2 forekomster av tallet to …

Runtime

$$\Theta (k)+\Theta (n)+\Theta (k)+\Theta (n)=\Theta (n+k)$$

Hvor $k$ er det største tallet i arrayen