In: Computer Science
A probability distribution function P(x) for a random variable X is defined by P(x) = P r{X ≤ x}. Suppose that we draw a list of n random variables X1, X2, X3 · · · Xn from a continuous probability distribution function P that is computable in O(1) time. Give an algorithm that sorts these numbers in linear average case time.