0
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Why did you mentioned "stable version of counting sort" ?Counting sort is a stable sort by default? $\endgroup$ – rahul sharma Nov 30 '17 at 16:51
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 30 '17 at 23:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.