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$
$\endgroup$
11
-
$\begingroup$ $\Omega (n)$ space to hold the input. Any comparison sort requires $\Omega ( n \log n)$ operations. What am I missing? $\endgroup$– Austin BuchananSep 19, 2013 at 15:29
-
$\begingroup$ no restriction to comparison sort. $\endgroup$– TurboSep 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
|
Show 6 more comments
1 Answer
$\begingroup$
$\endgroup$
7
Yes there is.
The best known deterministic algorithm in linear space runs in time within $O(n\lg\lg n)$ and was presented by Han in 2004.
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$– TurboSep 19, 2013 at 20:59
-
$\begingroup$ Is there a better than linear lower bound known? $\endgroup$– TurboSep 19, 2013 at 21:01
-
2$\begingroup$ See also this other Stack Exchange question: cstheory.stackexchange.com/questions/6642/… $\endgroup$ 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$– TurboSep 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$ Sep 20, 2013 at 10:42