1
$\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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
5
$\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)$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Why did you mentioned "stable version of counting sort" ?Counting sort is a stable sort by default? $\endgroup$
    – rahul sharma
    Nov 30, 2017 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, 2017 at 23:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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