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?
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this communityIs 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?
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".