[itamarst]

The bucket boundaries are often chosen from a random sample of the data, if the input data is very large. Sorting is O(nlogn), but using binary search per value to assign a bucket is O(n), plus the cost of creating the buckets on a sample. So once you hit a large enough number of values this scales better.

Binary search does give random access but in this case there's only up to 255 buckets typically, so it's random access on cached memory.

[wrsh07]

Can you say more about what happens for bucket assignment? Eg is it appending to a file or writing to a 2d array?

Agreed on linear vs n log n, ofc, and streaming considerations might also be relevant