A card shuffling algorithm is a method for randomly permuting a deck of cards so that every ordering is equally likely (in a “good” shuffle).
The most important and widely used algorithm is:
Fisher–Yates Shuffle (a.k.a. Knuth Shuffle)
This is the gold standard for unbiased shuffling.
Idea
You go through the deck from the last card to the first, and for each position, swap it with a randomly chosen earlier (or same) position.
Algorithm (array-based deck)
Let A be an array of n cards (array index: [0, ..., n-1]):
for i from n - 1 down to 1:
j = random integer such that 0 ≤ j ≤ i
swap A[i] and A[j]
Why it works
- Each card has an equal probability of ending in any position.
- It avoids subtle bias found in naive shuffles (like sorting with random comparator).
Complexity
- Time: O(n)
- Space: O(1) (in-place)
Variants you might see
1. Inside-out Fisher–Yates
Useful when building a shuffled array from scratch:
for i from 0 to n-1:
j = random integer in [0, i]
A[i] = A[j]
A[j] = current element
2. Riffle shuffle (card-deck realistic)
Models human shuffling:
- Split deck into two halves
- Interleave them probabilistically
Used in probability studies, but needs many repeats (~7 riffle shuffles) to approximate randomness.
Practical note
In most programming languages:
-
Use a built-in shuffle (e.g.,
random.shufflein Python), which implements Fisher–Yates.
