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?

How about randomized?

  • $\begingroup$ $\Omega (n)$ space to hold the input. Any comparison sort requires $\Omega ( n \log n)$ operations. What am I missing? $\endgroup$ – Austin Buchanan Sep 19 '13 at 15:29
  • $\begingroup$ no restriction to comparison sort. $\endgroup$ – 1.. Sep 19 '13 at 15:36
  • $\begingroup$ 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}$. $\endgroup$ – Jeffε Sep 19 '13 at 23:45
  • 1
    $\begingroup$ 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. $\endgroup$ – Jeffε Sep 20 '13 at 3:58
  • 2
    $\begingroup$ 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. $\endgroup$ – 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".

  • $\begingroup$ I am seeing the wiki. It makes sense now than before. $\endgroup$ – 1.. Sep 19 '13 at 20:59
  • $\begingroup$ Is there a better than linear lower bound known? $\endgroup$ – 1.. Sep 19 '13 at 21:01
  • 2
    $\begingroup$ See also this other Stack Exchange question: cstheory.stackexchange.com/questions/6642/… $\endgroup$ – Jeremy Sep 19 '13 at 21:15
  • $\begingroup$ 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 $\endgroup$ – 1.. Sep 19 '13 at 21:38
  • 1
    $\begingroup$ @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. $\endgroup$ – Jeremy Sep 20 '13 at 10:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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