Counting Sort

• Applies only to positive integers

Complexity

• Time
• $O(n + k)$
• $\Theta(n + k)$
• $\Omega(n + k)$
• Space
• $O(k)$

Where:

• $n$ is the total number of elements
• $k$ is the range from the min and max values in the original array