Random Shuffle Algorithms

A recent slashdot.org thread discussed how a programmer at Microsoft incorrectly implemented a random shuffle algorithm. The discussion was prompted by an article Rob Weir wrote in which he presented a comprehensive analysis of the problem and provided a correct algorithm. Along the way, he named the botched implementation the “Microsoft shuffle.”

The following points are salient:

1. One can use Pearson’s Chi-squared test to determine if the results are non-random. In Weir’s analysis, the probability that the results were random (the probability that the null hypothesis was true) was p < 2.2e–16, given 10,000 repetitions of the algorithm.
2. Random shuffle algorithms are so commonly used that this is often an interview question for a programmer.
3. The Fisher-Yates shuffle is an excellent random shuffle algorithm of time complexity O(n).
4. The programmer who implemented the Microsoft shuffle did not understand how a sorting algorithm works.

As usual with discussions on slashdot, there were quite a few posters who didn’t understand the problem and why it required an accurate solution.