Sort array of positive integers in specific range in O(n)

Asked Jan 25 '17 at 10:18

Active Jan 25 '17 at 10:42

Viewed 184 times

How can we sort an array A of positive integers in range [0,n^2/2] in O(n) time?
How can we sort the array if integers are in range [0,n^3/2] in O(n)?

I am new to algorithms. I would appreciate if someone explains the significance of the range along with the solution.

asked Jan 25 '17 at 10:18

Haroon S.

Possible duplicate of [Sorting in O(n) time?](http://stackoverflow.com/questions/19533693/sorting-in-on-time) – ilim Jan 25 '17 at 10:20
So, you have an unsorted list of n² / 2 numbers, say 500.000, and want to sort it in O(n), say, in on the order of 1.000 operations or swaps? – tobias_k Jan 25 '17 at 10:25
Try radix sort. – Raziman T V Jan 25 '17 at 13:01

0 Answers0