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.

This entry was posted in Computing. Bookmark the permalink.

2 Responses to Random Shuffle Algorithms

  1. pjm says:

    Perhaps those who didn’t understand should have been reading this thread at Coding Horror: http://www.codinghorror.com/blog/2010/02/the-nonprogramming-programmer.html

  2. Thanks for the link to that great article.

    – Conrad