Sort an array where $0\leq a_n\leq n^2$ and $a_n\in\mathbb{N}$ sort an array where $0\leq a_n\leq n$
sort an array where $0\leq a_n\leq n^2$(hint represent every element in base $n$)
All the elements are integers
for the first 1 I used counting sort and for the second one I thought maybe after changing to base $n$ using raddix?  ONe more thing,i've been asked to prove correctness for this first 1 but I've never see how to do this.
Any hints?
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)$.