I believe it’s also the algorithm that Ruby uses to implement its default
In terms of Big O notation, the Fisher-Yates algorithm’s Big-O grade is
O(n), because it touches every element only once. Here’s my implementation in Ruby:
Mike Bostock wrote an awesome, animated post on this algorithm, showing how other implementations fall short in important but non-obvious ways. So did Jeff Atwood: Jeff showed that if you implement this simply by counting up instead of down, the algorithm produces dangerously biased results.
I’m not a mathematician, and my first attempt at writing a custom shuffle algorithm did work naively. By contrast, the Fisher-Yates algorithm makes much more sense, to count away from the location of the group that is becoming randomized.