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 where the first item is the most likely candidate, but subsequent items are available if the primary fails.

The Starvation Problem

Sorting purely by success rate is a mistake. It directs 100% of traffic to the top service, leaving others with no traffic to prove they have recovered from a previous failure. We need weighted randomization to ensure every service gets "exploration" traffic.

The Better Way: Efraimidis-Spirakis

Instead of an iterative loop that picks and removes items, we can use a specialized form of Reservoir Sampling. The Efraimidis-Spirakis paper demonstrates that we can generate a weighted permutation in a single pass.

The logic is simple:

1. Generate a random double u between 0 and 1.
2. Calculate a sort key: u^(1/weight).
3. Sort the list by this key in descending order.

Scalability and Streams

This approach reduces complexity to O(N log N) and works perfectly for data streams. You can assign a sort key to an item the moment it arrives, making it ideal for high-throughput systems where performance is critical.

I've written a more detailed post on my personal blog that compares C# implementations and dives deeper into the math.

Check out the full post on my blog: https://byteaether.github.io/2026/the-weight-of-decisions-solving-weighted-random-sorting-at-scale/