Sorting an array in linear time
This is a textbook application of radix sort.

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)$.