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$ Commented 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$ Commented Nov 30, 2017 at 23:41

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.