# 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?

• Does the problem say $0\leq a_n\leq n$ or rather $0\leq a_k\leq n$, for $k=1,2,...,n$? – plop Nov 14 '20 at 16:21
• (The hint in the second part is a giveaway, rather.) – greybeard Nov 14 '20 at 16:58

You can make a list of length $$n^k$$ which $$k$$ is $$1$$ for the first case and $$2$$ for the second one.
Time complexity of this algorithm is $$O(n)$$.
Space Complexity is $$O(n^k)$$.