About sorting numbers in linear time
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&gt;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}$.