# Sorting an array in linear time

I need to find a method to sort an array in $O(n)$ time complexity. I saw this link, however I'm not sure how to apply it to the elements I need.

Input: an array $A$ of length $n$, containing values from $1$ to $n^2$

Output: a sorted array $A$

Can someone explain in pseudocode or in words how to do this?

Think of the inputs as 2-digit numbers in base $n$. Using a stable version of counting sort, sort the numbers first according to the least significant digit and then according to the most significant digits. Each pass takes $O(n)$, for a total running time of $O(n)$.
The same approach works for numbers up to $n^k$, and takes time $O(kn)$.