2
$\begingroup$

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?

$\endgroup$
11
  • $\begingroup$ $\Omega (n)$ space to hold the input. Any comparison sort requires $\Omega ( n \log n)$ operations. What am I missing? $\endgroup$ Sep 19, 2013 at 15:29
  • $\begingroup$ no restriction to comparison sort. $\endgroup$
    – Turbo
    Sep 19, 2013 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, 2013 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, 2013 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, 2013 at 12:48

1 Answer 1

6
$\begingroup$

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".

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

Your Answer

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

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