Given a list of items x1 ... xn and associated probabilties p1 ... pn that sum up to 1 there's a well known procedure to select a random item with its associated proabability by sorting the list according to weight, choosing a random value between 1 and 0, and adding up to a culmination sum until it exceeds the value selected and return the item at this point.

So if we have x1 -> 0.5, x2 -> 0.3, x3 -> 0.2, if the randomly chosen value is less than 0.5 x1 will be chosen, if between 0.5 and 0.8, x2, and else x3.

This requires sorting so it needs O(nlogn) time. Is there anything more efficient than that?