# How do I sort these elements in O(n) time?

So let's say I have an array of elements where each of the values can range from 0 to $n^2-1$. I'm trying to make an algorithm to sort this array in O(n) running time and I was thinking of using radix sort. The run time of radix sort is O(d(n+N)) or O(dn) if n is really large. So how can I modify radix sort so that it runs in O(n)?

EDIT: I don't think you guys understand this. The amount of elements in the array is n but the ACTUAL value for each element can range from 0 to n^2 - 1. So if we have an array with 10 elements in it then the largest the element can be is 99 and the smallest it can be is 0 but there will still be 10 elements in the array.

• I very much doubt that this is possible. All the sort algorithms I'm aware of that work faster than $\Theta(n\log n)$ have the restriction that there are only $O(n)$ possible different values in the data. Here, you have $\Theta(n^2)$ possible different values, so none of those tricks will work. Oct 29, 2015 at 8:57
• Actually this can work. Like I said, it's not just any value, the values in the array can only range from 0 to n^2-1 and there is a way to look at the values in a different way so you can use radix sort and sort the values in O(n) time. Remember that n is the number of elements in the array and d is the number of values in each key. So I'm trying to get it so that d is 1 therefore the run time is O(n). Oct 29, 2015 at 17:02
• I am pretty sure that the idea is to pick the base to be $n$. If you do, then each of the numbers has at most two digits (in the chosen base), and I believe the result follows. For the data structure course I TA, we normally have a question similar to this one, so I think the same trick applies. Oct 29, 2015 at 17:15
• "I don't think you guys understand this." Actually, I think I do and that you don't understand my comment. Let me rephrase. All the sorting algorithms I'm aware of that sort $n$ data items faster than $\Theta(n\log n)$ have the restriction that each data item must be one of the $n$ different values, such as $0, \dots, n-1$. Here, you still have $n$ items but each one of them can take any one of $n^2$ different values that each data item can have, so none of the tricks I know works. Oct 29, 2015 at 17:16
• "Actually this can work." -- if you are that convinced, why post the question? (Also, coming here for an expert opinion and then telling the experts, "you don't understand this", without giving a good reason for why this should be the case ... not an ideal strategy.)
– Raphael
Oct 29, 2015 at 18:41

If you want to implement this on a RAM with integer math (ie. a real computer if your n is smaller than $2^{32}$), you can have a look at Upper bounds for sorting integers on random access machines. The authors show that integers in the range [0,$n^c$] can be sorted in $O(n(1 + \log c))$. Word RAM models add some loglog factors to that runtime.

$d$ is presumably the number of digits, and you need $d = O(1)$.

Since the number of digits of a number $m$ in base $b$ is $1 + \lfloor \log_{b} m \rfloor$, you solve to get $b \approx m^{1/d}$.

Using base $n^2$ is too ambitious, but base $n$ or base $\sqrt{n}$ is fine, for example. (or better, pick the next larger power of $2$)

That is, rather than binning numbers based on their individual bits, you should bin them based on $\frac{1}{k} \log_2 n$ consecutive bits, for some integer $k \in O(1)$.

I really doubt anyone can sort an array within O(n) unless infinite memory is given. However, if you know the range of numbers and have sufficient memory to store all of them, then you can hash the array (take mod by $n^2$) and store them in a intermediate array of size ($n^2$).You can use another intermediate array of same size to store repetition (if you have repeated elements in original array.). All this can be done in single pass causing O(n). And on second pass iterate over the intermediate array and place them in original array one by one.

• How do you iterate over the O(n^2) sized intermediary array in O(n)? Oct 29, 2015 at 7:28
• And how would you access infinite memory in linear time? Or any finite amount of time? Oct 29, 2015 at 8:55
• I don't think you guys understand this. The amount of elements in the array is n but the ACTUAL value for each element can range from 0 to n^2 - 1. So if we have an array with 10 elements in it then the largest the element can be is 99 and the smallest it can be is 0 but there will still be 10 elements in the array. Oct 29, 2015 at 17:10
• @adrianN : One need not go over the array of size O(n^2). One can go over the hashed keys which can be done in O(n) and for this corresponding values you check the count in the intermediate array!! Nov 2, 2015 at 16:47
• @DavidRicherby : I might have written in a unclear manner (Pardon me for my bad English) . The idea that I was trying to imply was that if you have a infinite memory then you Hash any large number using a very big hashing value. So, that you enough place in memory for storing the unique values from the array. I wasnt implying to scan the infinite memory. Nov 2, 2015 at 16:51