2

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?

Turbo
  • 12,812
  • 1
  • 19
  • 68
  • $\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. – Turbo 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
  • That is why I am using the unit cost model which is similar to the Transdichotomous model as below – Turbo Sep 19 '13 at 23:49
  • 1
    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 03:58
  • @JɛffE Thankyou for the clarification. I meant 'similar' as in 'not totally similar' but I see the details now. I see your point on $2^{2^n}$. So an upper bound in unit-cost implies an upper bound in transdichotomous implies an upper bound in finite word-limited models and the opposite direction for lower bounds. Is my interpretation correct? If so, then my question seems correct? Is there a tighter upper bound in the unit cost model? – Turbo Sep 20 '13 at 12:20
  • In the wiki links below http://en.wikipedia.org/wiki/Integer_sorting#Trans-dichotomous_algorithms says "...., in which nothing is assumed about the range of the integer keys and one must bound the algorithm's performance by a function of the number of data values alone" while http://en.wikipedia.org/wiki/Transdichotomous_model says "....in which the machine word size is assumed to match the problem size". I took dichotomous model to be the former ambiguous one. Thankyou for the clarification again. I am really meaning a tighter linear upper bound in unit cost model... – Turbo Sep 20 '13 at 12:36
  • ... on whether they exist? I think the answer is no since even for the transdichotomous model the answer is 'not found' one yet. – Turbo Sep 20 '13 at 12:36
  • "Even a transdichotomous word RAM can only sort word-size integers in near-linear time. " Is this a proven lower bound? – Turbo Sep 20 '13 at 12:44
  • 2
    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
  • @JɛffE again thankyou for the comment. I was under the assumption that in the unit-cost model we can disregard the bit sizes of the words and hence reading and writing back can be done in $O(n)$. Is my understanding incorrect? I understand what you are saying is in the word RAM where bit specification of the integers matter when arithmetic operations and read write operations depend on the size of integers. My assumption was in the unit cost model the arithmetic operations and r/w operations are abstracted out at $O(1)$. I am implying this model. – Turbo Sep 20 '13 at 13:07

1 Answers1

6

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

J..y B..y
  • 2,776
  • 1
  • 22
  • 35
  • I am seeing the wiki. It makes sense now than before. – Turbo Sep 19 '13 at 20:59
  • Is there a better than linear lower bound known? – Turbo Sep 19 '13 at 21:01
  • 2
    See also this other Stack Exchange question: http://cstheory.stackexchange.com/questions/6642/hans-on-log-log-n-time-linear-space-integer-sorting-algorithm?rq=1 – J..y B..y 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 – Turbo Sep 19 '13 at 21:38
  • Another comment says "Anyway, even if the authors are correct, they neither achieve O(loglogn) sorting, nor explain Han, so not useful". So is Han's result correct? I am unchecking validation of the answer now. Is Han's result valid? – Turbo Sep 19 '13 at 21:40
  • Also Han's paper has the following as first line:"We present a fast deterministic algorithm for integer sorting in linear space. Our algorithm sorts n integers in the range {0,1,2, ..., m - 1} in linear space in O(n log log n) time". So they assume a range. – Turbo Sep 19 '13 at 21:43
  • 1
    @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. – J..y B..y Sep 20 '13 at 10:42