Shuffling looks trivial until you get it subtly wrong — and the "obvious" shuffle (for each slot, swap it with any random slot) is biased, favouring some orderings over others. Fisher–Yates does it right: walk from the last slot toward the first, and swap each element with a random one chosen only from the part not yet finalized. Every one of the n! orderings comes out equally likely, in a single O(n) pass. Step through it and watch the finalized region grow.
O(n) time · O(1) extra space · provably uniform over all n! permutations
unshuffled region
The front slots 0..i not yet finalized — the only place a swap partner is drawn from.
finalized region
The back slots i+1..n−1, already locked to their final values.
swap i ↔ j
Pick random j in [0, i], swap, then shrink i by one.
uniform
Every one of the n! orderings ends up equally likely.
shuffle.js — swap from the back, pick from the front
Ready
An array of 8 cards. We walk i from the last slot toward the first. At each step we pick a random j in [0, i] and swap — locking slot i to its final value.
7
cursor i
–
picked j
0
locked
How it works
The correctness rests on one careful choice: the random partner j is drawn from [0, i] — the unshuffled region includingi itself — never from the whole array. That single constraint is what makes the result uniform. The naive version that draws j from [0, n−1] looks almost identical and is quietly, provably biased.
1
Start at the last slot
Set the cursor i to n−1. Everything to its left is still up for grabs; nothing is finalized yet.
2
Swap with a random earlier (or equal) slot
Pick j uniformly in [0, i], swap a[i] and a[j]. Slot i now holds a uniformly-chosen element from the unshuffled region — and it is locked forever.
3
Shrink and repeat
Move i one step left and repeat, always drawing j only from the still-unshuffled prefix. When i reaches 0, the whole array is a uniform permutation.
✓
Why not draw j from the whole array?
The naive shuffle draws j from [0, n−1] every time. It produces n^n equally-likely execution paths, and n^n is not divisible by n! — so some orderings are strictly more likely than others. Fisher–Yates produces exactly n! paths, one per permutation.
Time
O(n)
Extra space
O(1)
Outcomes
n! equally likely
Naive bias
n^n ≠ k·n!
The code
# the modern (Durstenfeld) Fisher-Yates, in place, O(n)def shuffle(a):
for i in range(len(a) - 1, 0, -1): # from the back
j = random.randint(0, i) # j in [0, i] <- the key line
a[i], a[j] = a[j], a[i] # swap, lock slot ireturn a
# BIASED — do NOT do this: j spans the whole array every time# for i in range(len(a)): j = randint(0, len(a)-1); swap(a[i], a[j])
Quick check
1. Where must the random index j be drawn from at step i?
Drawing j from [0, i] is the whole trick. It guarantees each slot receives a uniformly random element from what remains, which makes all n! orderings equally likely. Drawing from the whole array is the biased naive version.
2. Why is the naive shuffle (j from [0, n−1] each step) biased?
The naive version makes n independent choices out of n options → n^n equally-likely execution paths. Since n^n is not a multiple of n! (for n > 2), those paths cannot spread evenly over the n! permutations — some orderings come up more often.
3. What is the time and extra-space cost of Fisher–Yates?
One pass, one swap per element, done in place — O(n) time and O(1) extra space. It’s both the fastest and the correct way to shuffle an array.
FAQ
What is the Fisher–Yates shuffle?
An algorithm that randomly permutes an array so all n! orderings are equally likely, in O(n) time and O(1) extra space. It walks from the last element to the first, swapping each with a random element from the not-yet-finalized portion.
Why is the naive shuffle biased?
It swaps each index with a random index from the entire array, making n^n equally-likely paths. Since n^n is not divisible by n! (for n > 2), those paths can’t spread evenly over the n! orderings — some come up more often.
Is Fisher–Yates the same as shuffling by sorting on random keys?
Sorting on random keys can also give a uniform shuffle (with distinct keys), but it costs O(n log n) and needs careful tie-breaking. Fisher–Yates is simpler, O(n), and in place — the standard choice.
Does the quality of the random number generator matter?
Yes — it’s only as uniform as its RNG. A weak or small-state generator makes many permutations unreachable; a 32-bit seed cannot produce most orderings of a 52-card deck, since 52! far exceeds 2^32. Use a high-quality RNG when fairness matters.