Shuffling - Shuffling Algorithms

Shuffling Algorithms

A computer is capable of generating a "perfect shuffle", a random permutation of the cards; beware that this terminology (an algorithm that perfectly randomizes the deck) differs from "a perfectly executed single shuffle", notably a perfectly interleaving faro shuffle. The Fisher–Yates shuffle, popularized by Donald Knuth, is simple (a few lines of code) and efficient (O(n) on an n-card deck, assuming constant time for fundamental steps) algorithm for doing this.

There are other, less-desirable algorithms in common use. For example, one can assign a random number to each card, and then sort the cards in order of their random numbers. This will generate a random permutation, unless any of the random numbers generated are the same as any others (i.e. pairs, triplets etc.). This can be eliminated either by adjusting one of the pair's values randomly up or down by a small amount, or reduced to an arbitrarily low probability by choosing a sufficiently wide range of random number choices. If using efficient sorting such as mergesort or heapsort this is an O(n log n) average and worst-case algorithm.

Other common ad-hoc algorithms try to emulate manual shuffling with poor success: the permutations they produce are usually far from random and the running times are poor.