How Shuffling Actually Works

The algorithm, one swap at a time

Start at the last position of the list. Pick a random position from the start of the list up to and including where you are, and swap the two items. Move one position to the left and repeat, always picking from the range that has not yet been finalised. Stop when you reach the first position.

That is the entire method. A ten-item list takes nine swaps; a fifty-two card deck takes fifty-one. Nothing is copied, nothing is sorted, and no item is ever considered twice.

• Walk from the end of the list toward the start.
• At each position i, draw a random index j between 0 and i inclusive.
• Swap the items at i and j.
• The item now at position i is final and is never touched again.

Why every ordering comes out equally likely

The argument is short and worth following, because it is what distinguishes a correct shuffle from one that merely looks shuffled.

On the first step there are n items and every one of them has an equal chance of being chosen for the last position — that is a 1-in-n chance each. On the second step, n−1 items remain and each has a 1-in-(n−1) chance of the second-to-last position. Multiply those probabilities all the way down and any specific complete ordering has probability 1 divided by n factorial.

Since there are exactly n factorial orderings and each has probability 1/n!, they are all equally likely, and none is unreachable. That is the definition of a uniform shuffle, and Fisher-Yates achieves it with the minimum possible number of random draws.

Bug one: drawing from the whole list instead of the remainder

The commonest error is choosing the swap partner from anywhere in the list rather than from the unfinalised range. It looks harmless, it produces output that is visibly shuffled, and it is measurably not uniform.

The reason is a counting mismatch. Drawing from the whole list every time gives n possibilities on each of n steps, so n to the power n equally likely execution paths. But there are only n factorial orderings, and n^n is not divisible by n! for n greater than 2 — so the paths cannot distribute evenly across the orderings, and some orderings must come out more often than others.

For a three-item list, the buggy version has 27 execution paths distributed across 6 orderings. Two of the orderings get 4 paths and four get 5, which means some orderings are 25% more likely than others. On a larger list the distortion is less obvious and does not go away.

Bug two: a biased random index

The second error is in the index draw rather than the algorithm. If the random index is produced by taking a remainder of a raw random byte — the classic `byte % (i+1)` — then some indices come up more often than others whenever the range does not divide evenly into 256.

Fisher-Yates makes n−1 index draws, so a small per-draw bias is applied repeatedly and compounds. The fix is rejection sampling: discard any byte that falls in the uneven leftover range and draw again. It costs a handful of extra draws and eliminates the bias entirely.

• The shuffle can be correct while the index draw is biased — both have to be right.
• Rejection sampling discards a small fraction of draws to make the remaining ones exactly uniform.
• The bias is invisible in output and only shows up in a frequency count over thousands of runs.

Checking a shuffle you did not write

The practical test is a frequency count. Shuffle a three-item list ten thousand times and tally how often each of the six orderings appears. A correct shuffle gives roughly 1,667 of each, with the variation you would expect from ten thousand samples — a spread of a few dozen either way.

A shuffle with the wrong-range bug gives a visibly lopsided table, with two orderings clearly under-represented. Three items is the right size for this test because six outcomes are easy to tally and the distortion is proportionally largest at small n.

For a larger list, the equivalent check is to track where a single item ends up. Shuffle a ten-item list ten thousand times and count how often item A lands in each position: a correct shuffle gives roughly a thousand per position.

What a shuffle does not give you

A uniform shuffle makes every ordering equally likely, which is not the same as making every ordering look random. The ordering that leaves the list unchanged is one of the n! possibilities and it is exactly as likely as any other — a ten-item list will come back unshuffled about once in every 3.6 million attempts, and that is correct behaviour.

It also gives no guarantee about local structure. Three items that were adjacent can remain adjacent, and a shuffled playlist can put three tracks by the same artist together — which is a real problem with a correct answer, covered separately.

Frequently asked questions

Tools that use this

Related guides