<p>Yes there is.</p>

<ol>
<li><p>The best known deterministic algorithm in linear space runs in time within $O(n\lg\lg n)$ and was presented by Han in 2004.</p></li>
<li><p>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. </p></li>
</ol>

<p>For more details, see the section on "<a href="http://en.wikipedia.org/wiki/Integer_sorting#Trans-dichotomous_algorithms">Trans-dichotomous algorithms</a>" from the wikipedia page for "<a href="http://en.wikipedia">Integer Sorting</a>".</p>

CC BY-SA 3.0
2013-09-19T20:59:01.613Z
I am seeing the wiki. It makes sense now than before.
Turbo
CC BY-SA 3.0
2013-09-19T21:01:51.827Z
Is there a better than linear lower bound known?
Turbo
CC BY-SA 3.0
2013-09-19T21:15:31.507Z
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
CC BY-SA 3.0
2013-09-19T21:38:25.760Z
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
CC BY-SA 3.0
2013-09-19T21:40:06.057Z
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
CC BY-SA 3.0
2013-09-19T21:43:25.410Z
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
CC BY-SA 3.0
2013-09-20T10:42:07.013Z
@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
CC BY-SA 3.0
2013-09-19T20:49:24.623Z
2013-09-19T20:49:24.623Z
J.y B.y
<p>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?</p>

<p>How about randomized?</p>

CC BY-SA 3.0
2013-09-19T15:29:09.340Z
$\Omega (n)$ space to hold the input. Any comparison sort requires $\Omega ( n \log n)$ operations. What am I missing?
Austin Buchanan
CC BY-SA 3.0
2013-09-19T15:36:47.030Z
no restriction to comparison sort.
Turbo
CC BY-SA 3.0
2013-09-19T23:45:58.527Z
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ε
CC BY-SA 3.0
2013-09-19T23:49:51.247Z
That is why I am using the unit cost model which is similar to the Transdichotomous model as below
Turbo
CC BY-SA 3.0
2013-09-20T03:58:59.023Z
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ε
CC BY-SA 3.0
2013-09-20T12:20:05.420Z
@JɛﬀE 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
CC BY-SA 3.0
2013-09-20T12:36:01.537Z
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
CC BY-SA 3.0
2013-09-20T12:36:38.650Z
... on whether they exist? I think the answer is no since even for the transdichotomous model the answer is 'not found' one yet.
Turbo
CC BY-SA 3.0
2013-09-20T12:44:09.393Z
"Even a transdichotomous word RAM can only sort word-size integers in near-linear time. " Is this a proven lower bound?
Turbo
CC BY-SA 3.0
2013-09-20T12:48:22.363Z
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ε
CC BY-SA 3.0
2013-09-20T13:07:24.973Z
@JɛﬀE 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
<sorting>
Best Sorting for unlimited integer range
Turbo
# Best Sorting for unlimited integer range

(Asked by: username_0 on 2013-09-19)

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?

**Tags:** sorting

> **Comments:**
> **username_1**: $\Omega (n)$ space to hold the input. Any comparison sort requires $\Omega ( n \log n)$ operations. What am I missing?  
> **username_0**: no restriction to comparison sort.  
> **username_2**: 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}$.  
> **username_0**: That is why I am using the unit cost model which is similar to the Transdichotomous model as below  
> **username_2**: 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.  
> **username_0**: @JɛﬀE 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?  
> **username_0**: 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...  
> **username_0**: ... on whether they exist? I think the answer is no since even for the transdichotomous model the answer is 'not found' one yet.  
> **username_0**: "Even a transdichotomous word RAM can only sort word-size integers in near-linear time. " Is this a proven lower bound?  
> **username_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.  
> **username_0**: @JɛﬀE 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.  

---

## 1 answers

### Answer by username_3 on 2013-09-19. Score: 6 | Accepted answer

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](http://en.wikipedia.org/wiki/Integer_sorting#Trans-dichotomous_algorithms)" from the wikipedia page for "[Integer Sorting](http://en.wikipedia)".

> **Comments:**
> **username_0**: I am seeing the wiki. It makes sense now than before.  
> **username_0**: Is there a better than linear lower bound known?  
> **username_3**: 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  
> **username_0**: 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  
> **username_0**: 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?  
> **username_0**: 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.  
> **username_3**: @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.  

---

