8.4-5

8.4-5 A probability distribution function P(x) for a random variable X is defined by P(x) = P(X \leq x). Suppose that we draw a list of n random variables X1,X2,...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.

P(x) is defined as cumulative probability distribution. ex: P(3) = P(0)+P(1)+P(2)+P(3). It is defined as sum of probabilities. These are uniformly distributed(wikipedia). Even if we add all these probabilities they are $\leq $ 1. This meets Bucket sort assumption about input to be uniformly distributed and lies between (0,1]. We can use bucket sort to sort the list of cumulative probabilities. A small adjustment should be made to bucket sort so it can handle 1 as a input as well since it is the maximum value.