# Best Sorting for unlimited integer range

Is there a better than time $O(n\log n)$ and space $O(n)$ deterministic algorithm in the RAM model to sort $n$ positive integers whose range is unbounded?

• $\Omega (n)$ space to hold the input. Any comparison sort requires $\Omega ( n \log n)$ operations. What am I missing? – Austin Buchanan Sep 19 '13 at 15:29
• no restriction to comparison sort. – 1.. Sep 19 '13 at 15:36
• It is not even possible to sort $n$ positive integers whose range is unbounded in $O(n \log n)$ time. Suppose, for example, that all $n$ integers are larger than $2^{2^n}$. – Jeffε Sep 19 '13 at 23:45
• No. The transdichotomous model is not the same as the unit-cost model; it requires a fixed word size. Even a transdichotomous word RAM can only sort word-size integers in near-linear time. You asked for unbounded integers, but the word size is a bound. – Jeffε Sep 20 '13 at 3:58
• In order for a word-RAM to sort $n$ integers in $O(n \text{polylog} n)$ time, it must be able to read those integers in $O(n \text{polylog} n)$ time, which implies they must occupy at most $O(n \text{polylog} n)$ words of memory, which implies that most of the integers use only $O(\text{polylog} n)$ words each. – Jeffε Sep 20 '13 at 12:48

Yes there is.

1. The best known deterministic algorithm in linear space runs in time within $O(n\lg\lg n)$ and was presented by Han in 2004.

2. The best known randomized algorithm in linear space runs in time within $O(n\sqrt{\lg\lg n})$ and was presented by Han and Thorup in 2012.

For more details, see the section on "Trans-dichotomous algorithms" from the wikipedia page for "Integer Sorting".

• I am seeing the wiki. It makes sense now than before. – 1.. Sep 19 '13 at 20:59
• Is there a better than linear lower bound known? – 1.. Sep 19 '13 at 21:01
• See also this other Stack Exchange question: cstheory.stackexchange.com/questions/6642/… – Jeremy Sep 19 '13 at 21:15
• thankyou for link. One of the comments mentions nlogn lower bound for comparison based sort which I already know and says general sorting does not have nlogn lower bound – 1.. Sep 19 '13 at 21:38
• @JAS: the research, wikipedia and stacks exchange communities are collaborative ones and provide but advices, neither is an oracle: on any result you have to decide for yourself. I did not study Han's result, but I tend to trust Mikkel's from 2012, if only by reputation. – Jeremy Sep 20 '13 at 10:42