[thomasahle]

The observation that "random numbers can be sorted in linear time" is actually often useful in algorithm design. A typical application is storing a sorted list of hash values.