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

## 1 Answer

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

• Why did you mentioned "stable version of counting sort" ?Counting sort is a stable sort by default? – rahul sharma Nov 30 '17 at 16:51
• I can imagine versions of counting sort that aren't stable, or indeed that may lose information. I'm not sure what the ISO standard version is like, though. – Yuval Filmus Nov 30 '17 at 23:41