Cairn
data structures · uniform random permutation of a known, in-memory collection · O(n) time, O(1) extra space

↩ back to Probabilistic

Fisher–Yates Shuffle

Every other Probabilistic entry on this site either builds up state from a stream one item at a time, replaces a rotation-based tree, or compares two items to each other. This one is simpler to state than any of those: given an array of n items already fully in memory, produce one permutation of it, chosen uniformly at random from all n! possibilities, touching the array exactly once and using no extra memory beyond a loop counter and a swap. Reservoir Sampling solves a related-sounding but genuinely different problem — picking a fair sample from a stream whose length isn't known in advance. This entry assumes the opposite: the whole collection is already sitting in an array, its length is already known, and the only question is what order to put it in.

The algorithm is named for Ronald Fisher and Frank Yates, who described the by-hand version in 1938 (cross out a name, roll dice, write it down, repeat). The in-place, O(n) computer version below is Richard Durstenfeld's 1964 "inside-out" reformulation, popularized by Knuth — different enough from the original pencil-and-paper procedure that it's sometimes called the Knuth shuffle, but it produces the identical uniform guarantee the 1938 version proves, just without ever needing a second array to cross names out of.

Try it

An 8-letter array, A through H, using a seeded random generator so the trace is identical every time you replay it. Click Next to run one iteration of the loop below — it swaps whichever position the loop is currently on with a uniformly drawn position from everything not yet finalized (which can be itself), then locks that position in for good and moves one step left. By the time the loop reaches position 0, every position has been visited exactly once.

array (8 items, seed fixed for a reproducible trace)
Click Next to run the first iteration.

Core operations

Why every permutation is equally likely

Think of the loop as filling the array from the back forward, one position at a time. When the loop reaches index i, exactly i + 1 items are still "unplaced" — the ones currently sitting in positions 0 through i — and the draw j ∈ [0, i] picks one of them, uniformly, to land in position i for good. That item is never touched again. So: position n − 1 is filled by a uniform choice among all n items (n possible outcomes), position n − 2 by a uniform choice among whichever n − 1 remain, and so on down to position 1, which chooses between the last 2, leaving position 0 with whatever's left (1 possible outcome, forced). Every step's choice is independent of every other step's, so the total number of equally likely choice sequences is n × (n−1) × ... × 2 × 1 = n! — and because each step permanently removes exactly the item it chose from all future choices, no two different choice sequences can ever produce the same final arrangement. That's a bijection between choice sequences and permutations, and since every choice sequence is equally likely, every permutation is too: probability exactly 1/n!, proved here and checked against real trial counts below.

One detail that looks like it should be a special case but isn't: the draw range [0, i] includes i itself, so roughly 1 time in i + 1 a step "swaps" an item with itself and nothing visibly changes. That's not wasted work to optimize away — it's required for the probabilities above to come out right. Leaving it in keeps every one of the i + 1 unplaced items, including the one already sitting at i, exactly as likely as any other to end up there. This is the same shape of mistake as Reservoir Sampling's own off-by-one pitfall (excluding the current item from a draw range "because it can't meaningfully choose itself") — there, narrowing the range produces an exact, provable skew rather than a crash; the same is true here, measured directly below.

Reference implementation

function shuffle(array) {
  for (let i = array.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1)); // uniform in [0, i]
    [array[i], array[j]] = [array[j], array[i]];
  }
  return array;
}

Verified in Node before any page prose was written. (1) The exact shipped demo trace — all seven iterations with the page's fixed seed reproduced standalone: i=7,j=5 · i=6,j=2 · i=5,j=1 · i=4,j=2 · i=3,j=3 (self-swap) · i=2,j=1 · i=1,j=0, taking ABCDEFGH to EAHDGBCF, matching the page's own demo exactly. (2) A 600,000-trial frequency sweep at n=3 (small enough to enumerate every one of the 3! = 6 possible outputs) using real Math.random(): every permutation landed within 0.001 of the theoretical 1/6 ≈ 0.1667. (3) The same sweep run against a deliberately shrunk range (j drawn from [0, i-1] instead of [0, i], dropping the self-swap case) confirmed the check would catch a broken implementation: two permutations came back measurably underrepresented, the predicted effect of narrowing the range described above. See the live trial button in Pitfalls below for the same discipline exposed directly on the page, not just asserted in prose.

Pitfalls

The single most common "shuffle" bug: drawing from the full range every step instead of shrinking it. It looks almost identical to the correct version:

// BROKEN: j drawn from the full [0, n) range every time, not shrinking to [0, i]
function naiveShuffle(array) {
  for (let i = 0; i < array.length; i++) {
    const j = Math.floor(Math.random() * array.length);
    [array[i], array[j]] = [array[j], array[i]];
  }
  return array;
}

This one isn't just "biased in practice" — it's mathematically incapable of being uniform, for a reason that doesn't need a single trial run to see. The loop makes n independent draws, each with n equally likely outcomes, so there are exactly n^n equally likely sequences of draws. For that to produce a uniform distribution over the n! permutations, n! would have to divide n^n evenly — and at n = 3, it already doesn't: 3^3 = 27 is not a multiple of 3! = 6. No implementation, no amount of care, no better random number generator can fix that; the pigeonhole is the proof. Worked out exactly for n = 3 by enumerating all 27 equally likely draw-sequences directly: three of the six permutations (including the identity, 0,1,2) come out with probability 4/27 ≈ 0.1481, and the other three come out at 5/27 ≈ 0.1852 — a real, exact, roughly 25% swing away from the correct 1/6 ≈ 0.1667 in both directions, not noise.

The second widely-copied idiom is worse, and the reason is different again:

// ALSO BROKEN: sorting with a random comparator is not a shuffle
array.sort(() => Math.random() - 0.5);

A comparator is supposed to answer a consistent question — "is A before or after B?" — and every real sort algorithm relies on that consistency to decide which comparisons it even needs to make. A comparator that answers randomly breaks that contract, so the result depends on the specific sort algorithm's own internal comparison pattern, not on anything resembling a fair shuffle. The exact bias is different in every JavaScript engine (V8, SpiderMonkey, JavaScriptCore each implement Array.prototype.sort differently), which is itself worth noticing — a "shuffle" whose fairness depends on which browser is running it was never actually a shuffle. One concrete illustration, measured in this site's own Node (V8) environment at n = 3 across 600,000 trials: the identity permutation 0,1,2 came back 37.5% of the time, against a correct 16.7% — more than double — while two other permutations dropped to about 6% each.

Run all three live, in whatever browser is reading this page right now — the exact numbers for the sort-based row will likely differ from the 37.5%/16.7% figures above (different engine, same underlying mistake), but the correct Fisher–Yates row should land close to uniform regardless:

observed frequency of each of the 6 possible orderings of [0, 1, 2]
Not run yet — click above.

There is a correct sort-based shuffle — it's just slower, for no benefit. Assign each item one fresh random number before sorting, store it, and sort by that fixed key instead of calling Math.random() inside the comparator:

// CORRECT, but O(n log n): each item gets exactly one random key, fixed before the sort begins
function sortKeyShuffle(array) {
  return array
    .map(item => ({ item, key: Math.random() }))
    .sort((a, b) => a.key - b.key)
    .map(({ item }) => item);
}

Because every item's key is drawn once and never changes mid-sort, the comparator is consistent again, and the final order is exactly as uniform as Fisher–Yates — confirmed in the same offline Node sweep above, within 0.001 of 1/6 on every permutation at n=3. The honest reason to prefer Fisher–Yates over this instead isn't correctness, it's that this version costs O(n log n) comparisons and an extra array of keys to buy nothing a single O(n) pass doesn't already give for free.

Where this shows up

Complexity

Time: O(n) — exactly n − 1 swaps, one random draw each, regardless of the data. Space: O(1) extra, beyond the array itself. The broken full-range version above costs exactly the same O(n) — fixing it is free; the bug was never about speed. The correct sort-by-fixed-key alternative is the one real time trade on this page: O(n log n) instead of O(n), plus an O(n) array of keys, bought for no accuracy gain over plain Fisher–Yates.

This site's guide, Choosing a Probabilistic Structure, groups this entry with Alias Method as the two Probabilistic entries that answer a one-shot question about a whole, already-known collection rather than a stream, a tree, or a pairwise comparison — and compares what each of those two one-shot questions actually is.