[CodesInChaos]

You can't just randomize the comparison operation, since that'd violate the requirements of a comparison function. MS made that mistake in their browser download dialog, which led to significant biases. You'd need to assign a random number to each item. But then you'd need to figure out a way to store this random number.

Also, for in-memory data comparison-based sorting is much slower than shuffling. Both asymptotically (O(n log n) vs O(n)) and in practice. I did not investigate if sorting algorithms not based on comparisons (e.g. radix sort) have competitive performance.

https://www.computerworld.com/article/2762287/microsoft-s-eu...

[ndriscoll]

If you wanted to go down that line of thinking, you should be able to use a hash function to uniformly shuffle the keys within a larger space, and then apply your sort to that. No need to store the randomized keys.

Probably performance wouldn't be as good as the OP article though.

[anonymoushn]

The technique in TFA is very similar to radix sort.