About sorting numbers in linear time

Question

• If one is given $n$ numbers picked uniformly at random from the interval $[0,1]$ then is it possible to sort them in linear time?

  It seems to me that some such method exists which uses binary representations of these numbers and compares the sequences of 0s and 1s between any two of them only partially and that somehow is enough!?

  What is confusing me is that this somewhere seems to need a source of random bits and that is not clear to me where. How many?

  Does one account for the time taken to generate these binary representations?

  • If the numbers are upper bounded by $n$ then apparently there is some probabilistic way of sorting them in linear time with a success guarantee $\geq 1 - \frac{1}{n^c}$ for some constant $c$.

  What is this method?

Answer 1

If your input consists of integers, that is your elements are from the set $\mathcal{U}=\{0,\ldots,u-1\}$, you can sort faster than $O(n\log n)$ assuming your model of computation is the word RAM.

• you can sort deterministically (even on using $\text{AC}^0$ computations) in time $O(n \log\log n)$
• there is a randomized algorithm that sorts in $O(n \sqrt{\log\log n})$
• if your word size $w=\log u$ is in $\Omega( \log^{2+\varepsilon} n)$ for some $\varepsilon>0$ then the input can be sorted in linear time

If you are interested in the references, check out Erik Demaine's lecture notes. Note that all these results use in some sense the effect that you can parallelize some computations on the word ram using bit tricks. It does not requires that the numbers are picked uniformly at random from $\mathcal{U}$.

Answer 2

Radix sorting runs in time $O(dn)$ where $d$ is the number of digits in each key and $n$ is the number of keys to be sorted. This is of course linear time only if $d$ is a constant. If the keys are unique and densely packed then $d$ is necessarily $\approx log(n)$, but if there are many repeated keys radix sorting can in theory sort significantly faster than the usual $O(n \log n)%$ methods.