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? 
About sorting numbers in linear time
sorting;probability theory;probabilistic algorithms