Moving Beyond O(N^2 log N) for Weighted Random Sorting

In high-volume traffic routing, we often need a "fail-over" list: a fully sorted list of destinations...