# Sorting some set of number

Let $U=\{1,2,3\cdots m-1\}$ and some $n$ keys from $U$. Is it possible to sort these $n$ keys in $O(n \log \log n)$ time using $O(n)$ space?

Model of computation is RAM.

The algorithm is studied by Yijie Han in his paper [1].

There's also a relevant question on cstheory: Han's $O(n\log\log n)$ time, linear space, integer sorting algorithm.

• It seems the paper uses $\Theta(n+m)$ spaces. – xskxzr Aug 8 '18 at 0:38

I think you may need to clarify your question. It is certainly not possible as written, because the running time and space usage should depend on $m$, not just on $n$.

In particular, if $m$ is very large, then $n$ numbers may take a large amount of space to write out in the first place, which immediately lower bounds the running time.

• Is it possible to do in $O(n \log \log n)$ space wth the time mentioned in the question. – old Aug 7 '18 at 8:40
• @old You sort a list, not a set. A set is not ordered. It is not clear what you want to sort. – xuq01 Aug 7 '18 at 10:52
• (1) In the usual RAM model, every memory cell holds a machine word of length $O(\log N)$ bits, where $N$ is the length of the input in bits, and operations on a single machine word take $O(1)$ time. In this case, assuming the standard encoding, $N = n\log m$, and so we are allowed constant time operations on words of length $O(\log n + \log \log m)$ bits. (2) Space consumption doesn't include the input. (3) OP might have meant to use $N$ rather than $n$ in their time and space requirements. – Yuval Filmus Aug 7 '18 at 23:28
• @YuvalFilmus Thanks for your comment, I only have a vague understanding of the RAM model so I maybe should not have answered. I upvoted your comment and your own answer for visibility. – 6005 Aug 8 '18 at 0:14
• That's OK, nobody understands the RAM model... – Yuval Filmus Aug 8 '18 at 0:15

It is possible to sort them in $O(n)$ time using $O(1)$ extra space. So yes.

• This is for words of size $O(\log n)$, that is, when $m$ is polynomial in $n$. – Yuval Filmus Aug 8 '18 at 1:13
• Yes, that's the word RAM model. – Pseudonym Aug 9 '18 at 5:49