Sort an array where $0\leq a_n\leq n^2$ and $a_n\in\mathbb{N}$
You can make a list of length $n^k$ which $k$ is $1$ for the first case and $2$ for the second one.
So you have an array and you can put each element in the relevant position. This idea may waste space but it's fast.
Time complexity of this algorithm is $O(n)$.
Space Complexity is $O(n^k)$.