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:
- 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.
- Random shuffle algorithms are so commonly used that this is often an interview question for a programmer.
- The Fisher-Yates shuffle is an excellent random shuffle algorithm of time complexity O(n).
- 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.