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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityLet $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.
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.
It is possible to sort them in $O(n)$ time using $O(1)$ extra space. So yes.