Fisher-Yates Shuffle: Why Random Sorting Isn't Just About Random Numbers

You click "Shuffle"—but is the result truly random? Most people assume that calling a random number function is all it takes to get a fair, unbiased permutation. In practice, the wrong implementation quietly skews probabilities, making some orderings far more likely than others. This article walks through the Fisher-Yates shuffle algorithm: what it is, why it works, and how to implement it correctly.

1. What Does "Fair Random Permutation" Mean?

Suppose you have 3 elements [A, B, C]. There are 3! = 6 possible orderings:

ABC  ACB  BAC  BCA  CAB  CBA

A fair shuffle means each of these 6 orderings appears with exactly 1/6 ≈ 16.67% probability. If a particular implementation makes ABC appear 20% of the time while others appear only 16%, that shuffle is biased—even if the output "looks random" to the eye.

2. The Common Pitfall: sort() + Math.random()

Many developers have written something like this (JavaScript):

// Common but biased approach
array.sort(() => Math.random() - 0.5);

This looks reasonable but introduces real statistical bias for two reasons:

Sorting algorithms expect consistent comparisons: Quicksort and mergesort may compare the same pair of elements multiple times, expecting a stable answer. A random comparator can flip its answer between calls, leading the algorithm down unintended paths.
Not enough entropy: A comparison-based sort makes O(n log n) comparisons, but there are n! possible permutations. When n! greatly exceeds the number of distinguishable outcomes from those comparisons, certain permutations inevitably get "merged" and receive higher probability.

Statistical proof

Run sort+random on [1,2,3] one million times. Some permutations appear ~20% of the time instead of the expected 16.67%. The bias is small but unacceptable in any context requiring fairness.

3. The Fisher-Yates Algorithm

Fisher-Yates Shuffle (also called Knuth Shuffle in its modern form) was introduced by Ronald Fisher and Frank Yates in 1938 and popularized by Donald Knuth in The Art of Computer Programming.

Algorithm steps for an n-element array:

Start at the last element (index n-1) and iterate toward index 1.
For the current index i, pick a random index j uniformly from [0, i] (inclusive).
Swap array[i] with array[j].
Move to index i-1 and repeat until i = 1.

// Fisher-Yates Shuffle — correct JavaScript implementation
function shuffle(array) {
    const a = [...array]; // don't mutate the original
    for (let i = a.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [a[i], a[j]] = [a[j], a[i]]; // swap
    }
    return a;
}

4. Why Fisher-Yates Guarantees Uniform Distribution

Walk through the probability for [A, B, C]:

Step	Operation	Probability
i=2	Choose j from [0,1,2] — determines which element goes in position 3	1/3 each
i=1	Choose j from [0,1] — determines which element goes in position 2	1/2 each
i=0	Position 1 gets the remaining element	1

Probability of any specific permutation:

P(specific permutation) = 1/3 × 1/2 × 1 = 1/6

Perfectly uniform. For n elements, each permutation appears with exactly 1/n! probability, provided the underlying random number generator is itself uniformly distributed.

5. The Importance of a Good Random Source

Fisher-Yates is only as fair as the random number generator it uses. Quality varies by environment:

Environment	Function	Use Case
JavaScript (browser)	`Math.random()`	General draws, games (non-cryptographic)
JavaScript (high quality)	`crypto.getRandomValues()`	Secure draws, lottery systems
Python	`random.shuffle()`	General use (Fisher-Yates built in)
Python (secure)	`secrets.SystemRandom().shuffle()`	Cryptographic-strength requirements
PHP	`shuffle()`	General use

For everyday use cases—classroom grouping, activity draws—Math.random() is more than sufficient. For draws with legal or financial stakes, use a cryptographically secure source.

6. From Shuffle to Groups

"Random grouping" is simply "shuffle + round-robin assignment" combined:

function randomGroup(names, groupCount) {
    const shuffled = shuffle(names);               // Step 1: Fisher-Yates
    const groups = Array.from({ length: groupCount }, () => []);
    shuffled.forEach((name, i) => {
        groups[i % groupCount].push(name);          // Step 2: round-robin
    });
    return groups;
}

Round-robin assignment (i % groupCount) ensures groups differ by at most 1 person. For 10 people in 3 groups you get 4–3–3, not the less balanced 4–4–2.

7. Common Mistakes at a Glance

Mistake	Problem	Fix
array.sort(() => Math.random() - 0.5)	Statistically biased	Use Fisher-Yates
Assign a random key to each element, then sort	Correct in theory but O(n log n)	Fisher-Yates is O(n)
Pick only the first n random elements	Incomplete shuffle	First k steps of Fisher-Yates = k-sample without replacement
Swap each position with itself multiple random times	Non-uniform swap probability	Each position gets exactly one swap

Bonus: partial shuffle = sampling without replacement

Run only the first k iterations of Fisher-Yates to randomly select k items from n, with no repetition. Time complexity O(k)—no need to shuffle the entire array. Perfect for prize draws and random quiz questions.

8. Summary

Shuffling looks trivial but "visually random" and "statistically uniform" are different things. Fisher-Yates delivers O(n) performance with mathematical proof of uniformity—the industry-standard choice for any application where fairness matters, from classroom groups to card games.

Want to see it in action? Try the List Grouping & Random Sort tool on this site—enter any list and get a provably fair shuffle or group split instantly.