Introduction to the Fisher-Yates Shuffle

The Fisher–Yates shuffle is an algorithm for rearranging a finite sequence into a random order such that every possible ordering, every permutation of the sequence, occurs with exactly the same probability. It runs in place, touching each position exactly once, and needs no extra memory beyond a single temporary during each swap.

The method traces back to a paper-and-pencil procedure published by Ronald Fisher and Frank Yates in 1938 in Statistical Tables, intended for manually drawing random samples. The version used on computers today, which processes the sequence in a single linear pass rather than repeatedly searching a shrinking list, was described by Richard Durstenfeld in 1964 and later popularized by Donald Knuth in The Art of Computer Programming, which is why it is also called the Knuth shuffle.

The Algorithm

Given an array \(a\) of \(n\) elements at indices \(0,\dots,n-1\), the algorithm processes the positions from the end toward the front. At each position \(i\), it draws a uniformly random index \(j\) from the elements not yet placed, that is, from \(0\) through \(i\) inclusive, and swaps the two:

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

An equivalent formulation runs the same idea from front to back, drawing the swap partner for position \(i\) from the elements at or after \(i\):

function shuffleForward(a) {
  for (let i = 0; i <= a.length - 2; i++) {
    const j = i + Math.floor(Math.random() * (a.length - i));
    [a[i], a[j]] = [a[j], a[i]];
  }
  return a;
}

The two variants are mirror images of each other: relabeling every index \(k\) as \(n-1-k\) turns one loop into the other, so any statement proved for one transfers immediately to the other. Both make exactly \(n-1\) random draws and \(n-1\) swaps, and both touch every position exactly once.

Worked Example

Tracing the backward algorithm on a five-letter array makes the bookkeeping concrete. Start from \(a=[A,B,C,D,E]\) and suppose the random draws happen to be \(j=1,3,0,1\) for \(i=4,3,2,1\) in turn:

The loop stops once \(i=0\) is reached, since the single remaining element has nowhere else to go. The final array, \([C,E,A,D,B]\), is one specific outcome out of \(5!=120\) equally likely ones; a different sequence of draws for \(j\) would trace an entirely different path to a different, but equally likely, permutation.

Why the Algorithm Can Run In Place

At the start of the step for index \(i\), positions \(i+1,\dots,n-1\) already hold their final, shuffled values, drawn without replacement from the original elements, while positions \(0,\dots,i\) hold exactly the elements that have not yet been placed, in some order that never needs to be tracked separately. The array is always partitioned into these two contiguous regions, and together they always account for all \(n\) elements.

The swap at step \(i\) does two things at once: it moves a uniformly chosen element out of the unplaced region into its final resting place at position \(i\), and it moves the element that had been sitting at position \(i\) back into the unplaced region, at the slot \(j\) that was just vacated. Because both effects happen through the same single exchange, the algorithm never needs a second array to collect the shuffled output or to track which elements remain: the one array already stores both regions, and the boundary between them is simply the loop counter \(i\).

Why the Range Has to Shrink

The detail that makes this algorithm work, rather than merely look plausible, is that the range of the random index \(j\) shrinks by one at every step. It is tempting to instead draw \(j\) uniformly from the full range \(0,\dots,n-1\) at every iteration:

function shuffleNaive(a) {
  for (let i = 0; i <= a.length - 1; i++) {
    const j = Math.floor(Math.random() * a.length);
    [a[i], a[j]] = [a[j], a[i]];
  }
  return a;
}

This variant still produces some permutation of the array, but not a uniformly random one, and a short counting argument shows this is unavoidable rather than just unlucky in practice. The loop makes \(n\) independent draws, each with \(n\) possible outcomes, so there are exactly \(n^n\) equally likely sequences of draws in total. If the resulting permutations were uniformly distributed, each of the \(n!\) permutations would have to be produced by exactly \(n^n/n!\) of those sequences, which requires \(n!\) to divide \(n^n\) evenly. Already for \(n=3\), \(n^n=27\) and \(n!=6\), and \(27/6=4.5\) is not an integer, so the \(27\) equally likely draw sequences cannot possibly split into six equal groups: some permutations of three elements must occur more often than others. The bias is small for small \(n\), but it never disappears and grows more pronounced as \(n\) increases: for six elements, \(6^6=46656\) candidate sequences would have to divide evenly across \(6!=720\) permutations, and \(46656/720=64.8\) confirms once again that they cannot.

The correct algorithm avoids this by construction. Because the range at step \(i\) (in the backward version) has exactly \(i+1\) possible values, the total number of distinct draw sequences over the whole run is

\[ \prod_{i=1}^{n-1}(i+1) = 2\cdot 3\cdots n = n!, \]

which is exactly the number of permutations of \(n\) elements. This numerical coincidence is necessary for a uniform result, though not yet sufficient on its own; the next section shows that the map from draw sequences to permutations is in fact a bijection, which together with this count is what pins down a uniform distribution over all \(n!\) outcomes.

Correctness: Every Permutation Is Equally Likely

The claim is that after running the backward algorithm on an array of \(n\) elements, each of the \(n!\) possible orderings of those elements occurs with probability exactly \(1/n!\). The proof proceeds by induction on \(n\), and it establishes the slightly stronger statement that this holds for any fixed starting arrangement of the elements, since the algorithm's only source of randomness is its own internal draws, never the input order.

Base case. For \(n=1\) there is only one permutation and the loop performs no draws at all, so that single outcome occurs with probability \(1\), matching \(1/1!\).

Inductive step. Assume the claim holds for arrays of \(n-1\) elements: run on any fixed starting arrangement of \(n-1\) elements, the algorithm produces a uniformly random permutation of them. Now consider an array of \(n\) elements, in some fixed starting order \(a_0,\dots,a_{n-1}\). The first step of the loop, at \(i=n-1\), draws \(j\) uniformly from \(\{0,\dots,n-1\}\) and swaps \(a_{n-1}\) with \(a_j\).

Since \(j\) is uniform over all \(n\) indices, each of the \(n\) elements \(a_0,\dots,a_{n-1}\) ends up at the final position with the same probability \(1/n\); the case \(j=n-1\) simply leaves \(a_{n-1}\) where it already was, and is one of the \(n\) equally likely outcomes like any other. Whichever element lands last, the remaining \(n-1\) elements now occupy positions \(0,\dots,n-2\) in some order: the original sequence with position \(j\) overwritten by what used to be at position \(n-1\). This is a fully determined rearrangement once \(j\) is fixed, but crucially it is still just some fixed arrangement of a known set of \(n-1\) elements.

The rest of the loop, for \(i=n-2\) downto \(1\), is exactly the \((n-1)\)-element version of the algorithm applied to this sub-array, using draws that are independent of the first step's draw. By the induction hypothesis, applying it to any fixed arrangement of \(n-1\) elements yields a uniformly random permutation of them, each with probability \(1/(n-1)!\), regardless of which arrangement it started from.

Combining the two independent stages: for any target element \(x\) and any target ordering \(\sigma\) of the remaining \(n-1\) elements,

\[ P(\text{last element}=x \text{ and rest ordered as } \sigma) = P(\text{last element}=x)\cdot P(\text{rest}=\sigma \mid \text{last element}=x) = \frac{1}{n}\cdot\frac{1}{(n-1)!} = \frac{1}{n!}. \]

Every permutation of the full array corresponds to exactly one choice of last element together with one ordering of the rest, so every permutation occurs with probability \(1/n!\). This completes the induction, and by the earlier mirror-image argument, the forward variant is unbiased as well.

An Equivalent View: Counting Draw Sequences

The induction above can be repackaged as a counting statement, which also explains why the algorithm is sometimes introduced through an urn analogy: picking elements one at a time out of a jar without looking, and lining them up in the order they are drawn, produces a uniformly random arrangement because every element is equally likely to be drawn at every stage, independent of what has already been removed.

The shuffle performs the same kind of sequence of independent, uniform, shrinking-range choices, just implemented as swaps within a single array instead of moves between two containers. Since there are exactly \(n!\) equally likely draw sequences and the inductive argument shows the map from draw sequences to resulting permutations is one-to-one, every permutation is the image of exactly one draw sequence, and since all draw sequences are equally likely, so are all permutations.

Complexity

The algorithm makes exactly \(n-1\) random draws and \(n-1\) swaps, giving \(O(n)\) time. It operates in place, requiring only \(O(1)\) additional space for the temporary value used during a swap, in contrast to methods that assign each element a random sort key and re-sort the array, which need \(O(n\log n)\) time for the sort and are not guaranteed to be unbiased unless the keys are drawn from a sufficiently fine-grained distribution and the sort is a genuine total order.

Two other approaches are sometimes used instead, and both remain unbiased while giving up the linear running time. The first repeatedly draws a uniformly random index from the full range \(0,\dots,n-1\), keeps track of which indices have already been used, and discards and re-draws on a duplicate. Each accepted draw is still uniform over the genuinely remaining elements, so the result is unbiased, but the number of draws needed to collect all \(n\) distinct indices is the classical coupon collector problem, whose expectation is

\[ n\sum_{k=1}^{n}\frac{1}{k} = nH_n \approx n\ln n, \]

so this variant costs \(\Theta(n\log n)\) expected time, purely from wasted duplicate draws that have to be thrown away and retried.

The second approach keeps a working list of the not-yet-shuffled elements and repeatedly removes a uniformly random one from it, appending it to a separate output list. This also draws from a correctly shrinking range and is therefore unbiased, but removing an element from the middle of a contiguous array requires shifting every subsequent element down by one to close the gap, an \(O(\text{size})\) operation; with an average remaining size of about \(n/2\) across the \(n\) removals, the total cost is \(O(n^2)\), and it needs a second array besides.

The in-place swap avoids both costs at once: no duplicate draws are ever wasted, since the range already excludes placed elements, and no shifting is ever needed, since the placed element and the freed slot trade positions directly.

Visualizing the Bias

A convenient way to check whether a shuffle is unbiased is to track, over many independent runs, which final position each starting element ends up in. Cell \((s,p)\) in the grid below counts how often the element that started at position \(s\) ended at position \(p\), out of the chosen number of trials. Since every element should end up at every position with probability \(1/n\), an unbiased shuffle keeps every cell close to the same expected count, rendering as a flat, uniform grid; a biased shuffle instead shows a visible pattern of over- and under-represented cells.

Application: Pairing Two Groups Uniformly at Random

Shuffling two equal-size arrays independently and then pairing them up index by index produces a uniformly random one-to-one pairing between the two groups: since each shuffle is independent and uniform over its own \(n!\) orderings, the combined result is uniform over all \(n!\) possible pairings between the groups, which is useful for tasks such as randomized partner assignment or matching participants across two pools without favoring any particular pairing.

Common Pitfalls

• Drawing \(j\) from the full range \(0,\dots,n-1\) at every step, instead of the shrinking range \(0,\dots,i\), produces a biased result, as shown by the counting argument above; this is one of the most common implementations of this algorithm found in the wild.
• Assigning each element a random key and sorting by it is only unbiased if the sort compares keys with a true total order and no two keys collide; sorting with a random comparator such as a function that returns a fresh random value on every call is not a valid substitute, since it can violate the transitivity a correct sort relies on and its output distribution then depends on the internal behavior of the specific sorting algorithm rather than on the randomness alone.
• The random index generator itself has to be uniform over the required range; a generator with a smaller period than the number of distinct draw sequences it needs to produce cannot realize all of them, which silently reintroduces bias for large \(n\).

Key Results

• The Fisher–Yates shuffle rearranges \(n\) elements in place using \(n-1\) swaps, each against a uniformly drawn index from a shrinking range.
• Correctness follows by induction: at each step, every remaining element is equally likely to be placed next, and the two stages of the argument are independent.
• The correct range gives exactly \(n!\) equally likely draw sequences, matching the number of permutations; keeping the range fixed at \(n\) gives \(n^n\) sequences, which generally does not divide evenly by \(n!\) and is therefore biased.
• The algorithm runs in \(O(n)\) time and \(O(1)\) extra space; reject-and-retry sampling is unbiased but costs \(\Theta(n\log n)\) expected time from the coupon collector effect, and removing elements from a shrinking list costs \(O(n^2)\) from the shifting needed to compact it.
• Tracking, over many trials, which final position each starting element reaches exposes bias directly: a uniform grid of counts indicates an unbiased shuffle, while visibly hot and cold cells indicate one that is not.