What is the Fisher-Yates Shuffle Algorithm?
Learn how the Fisher-Yates shuffle produces a uniform random permutation in O(n) time and avoids the classic naive-shuffle bias.
Expected Interview Answer
The Fisher-Yates shuffle is an in-place algorithm that produces a uniformly random permutation of an array in O(n) time by iterating from the last index to the first and swapping each element with a randomly chosen element at or before its own position.
Starting at the last index i = n-1 and moving down to i = 1, the algorithm picks a random index j in the range [0, i] and swaps array[i] with array[j], then shrinks the active range by moving to i-1. Each element is swapped exactly once into its final resting position, and because the random index at each step is drawn uniformly from a shrinking range, every one of the n! possible orderings is equally likely — this is the key property that distinguishes it from naive shuffles. A common bug, sometimes called the 'naive shuffle', picks j from the full range [0, n-1] at every step instead of the shrinking [0, i] range; this biases the output toward certain permutations because some final positions become reachable through more paths than others. Fisher-Yates runs in O(n) time and O(1) extra space, making it the standard choice for card shuffling, randomized test data, and sampling without replacement.
- O(n) time, single pass, in-place
- Produces a mathematically uniform random permutation
- O(1) extra space beyond the array itself
- Avoids the bias of naive full-range random swapping
AI Mentor Explanation
Fisher-Yates is like a groundskeeper assigning batting order by walking from the last batting slot to the first, and for each slot drawing a name only from the players not yet placed. Slot 11 draws from all 11 remaining names, slot 10 draws only from the 10 names still unassigned, and so on down to slot 1 which has just one name left. Because the pool shrinks by exactly one candidate at each step, every possible batting order is equally likely to occur. If the groundskeeper instead redrew from all 11 names at every slot, some orders would come up far more often than others, which is exactly the bias Fisher-Yates avoids.
Step-by-Step Explanation
Step 1
Start at the last index
Set i = n - 1, the last valid index of the array.
Step 2
Pick a random index in the shrinking range
Draw j uniformly from [0, i], not from the full array range.
Step 3
Swap and shrink
Swap array[i] and array[j], then decrement i by 1 and repeat until i = 1.
Step 4
Verify uniformity
Because each step draws from a strictly shrinking pool, all n! permutations are equally likely.
What Interviewer Expects
- Explain the shrinking-range invariant [0, i], not the full array range
- State O(n) time and O(1) extra space
- Identify the naive-shuffle bug (drawing from the full range every time) and why it biases results
- Give real use cases: card shuffling, randomized test ordering, sampling without replacement
Common Mistakes
- Drawing the random index from the full array range at every step (the classic naive-shuffle bug)
- Iterating forward from index 0 instead of backward from the last index (also valid, but frequently implemented incorrectly)
- Believing Array.sort with a random comparator produces a uniform shuffle (it does not, generally)
- Forgetting the algorithm is in-place and needs no extra array
Best Answer (HR Friendly)
“The Fisher-Yates shuffle is the correct way to randomly shuffle a list so every possible ordering is equally likely. I walk from the end of the list to the start, and for each position I swap it with a random element chosen only from the positions not yet finalized, which is what makes the shuffle mathematically fair instead of subtly biased.”
Code Example
import random
def fisher_yates_shuffle(arr):
for i in range(len(arr) - 1, 0, -1):
j = random.randint(0, i) # shrinking range [0, i], not [0, n-1]
arr[i], arr[j] = arr[j], arr[i]
return arr
deck = list(range(52))
fisher_yates_shuffle(deck)
print(deck) # a uniformly random permutationFollow-up Questions
- Why does drawing the random index from the full range instead of [0, i] bias the shuffle?
- How would you prove Fisher-Yates produces all n! permutations with equal probability?
- How is Fisher-Yates related to reservoir sampling?
- How would you shuffle a very large dataset that does not fit in memory?
MCQ Practice
1. What is the time complexity of the Fisher-Yates shuffle on an array of n elements?
The algorithm makes exactly one pass through the array, swapping each element once, giving O(n) time.
2. At step i in the standard backward Fisher-Yates shuffle, what range should the random index j be drawn from?
Drawing from the shrinking range [0, i] at each step is what guarantees a uniform random permutation.
3. What bug results from drawing the random swap index from the full array range at every step?
This is the classic naive-shuffle bug: some final orderings become reachable via more swap paths than others, skewing the distribution.
Flash Cards
What does the Fisher-Yates shuffle guarantee? — A uniformly random permutation, where all n! orderings are equally likely.
What is Fisher-Yates's time and space complexity? — O(n) time and O(1) extra space, done in place.
What range must the random swap index be drawn from at step i? — The shrinking range [0, i], not the full array range.
What is the classic naive-shuffle bug? — Drawing the random index from the full array range at every step, which biases the resulting permutation.