The Fisher-Yates Shuffle Explained

Why shuffling needs a proper algorithm

Putting a list into random order sounds easy, but many home-made methods quietly favour some orderings over others. Sorting a list by a random number, or swapping items around “a few times”, can look random while producing results that are measurably uneven. For a giveaway, that matters: if some positions in the shuffled list are more likely than others, some entrants have a better chance than they should.

The Fisher-Yates shuffle is the standard answer to this problem. It is short, fast and, when fed good random numbers, gives every possible ordering exactly the same probability. That property is what people mean by an unbiased shuffle.

Where the name comes from

Ronald Fisher and Frank Yates described the method in 1938 in their book Statistical Tables for Biological, Agricultural and Medical Research. It was designed for pencil and paper: you wrote the items down, used a table of random numbers to pick one, crossed it out and wrote it at the end of a new list, then repeated until nothing was left.

In 1964 Richard Durstenfeld published the version computers use today. Instead of crossing items out and counting the remaining ones, it swaps the chosen item with the last item that has not yet been chosen, which is quicker. Donald Knuth later popularised this form in The Art of Computer Programming, which is why you will also see it called the Knuth shuffle.

How the modern version works

Imagine your entries in a row. The algorithm works from the end of the row towards the start, and at each step it does the same three things:

1. Look at the positions that have not been fixed yet, from the first one up to the current position.
2. Pick one of those positions at random, with every position equally likely.
3. Swap the item in the chosen position with the item in the current position, then treat the current position as final and move one step towards the start.

When the process reaches the beginning, every item has been placed. Each item is touched a small, fixed number of times, so a list of ten thousand entries is no harder to shuffle than a list of ten, and the work grows in direct proportion to the list length.

Why the obvious shuffle is biased

A tempting shortcut is to go through the list once and swap every item with a randomly chosen item from the whole list. It looks fair, but it is not. For a list of n items, that approach has n × n equally likely sequences of swaps, while there are only n! (n factorial) different orderings. Those two numbers do not divide evenly, so some orderings must come up more often than others.

Take just three items. The shortcut has 27 equally likely swap sequences but only six orderings, and 27 cannot be split evenly six ways. Some orderings arise from four of the sequences and others from five. Fisher-Yates avoids this because the number of choices shrinks at each step, so the total number of outcomes is exactly n!, one for each ordering.

The random numbers matter too

The algorithm is only as fair as the numbers feeding it. Two issues are worth knowing about. The first is the quality of the generator. Ordinary programming-language random functions are designed for speed and are not meant to be unpredictable, whereas browsers provide a cryptographically secure source through crypto.getRandomValues(), which is designed so that results cannot be predicted from earlier output.

The second issue is modulo bias. Generators return numbers in a fixed range, and a common trick is to take the remainder after dividing by the size you need. If the generator’s range is not an exact multiple of that size, some results come up slightly more often than others. As a simple example, reducing a 0–99 source to 0–15 makes the values 0–3 about 17% more likely than the rest. The standard fix is to discard any value that falls in the uneven leftover part and draw again, so that every remaining outcome is equally likely.

Putting it to work in a giveaway

For a winner draw, the usual approach is to shuffle the entire entry list and then read the winners from the top: the first name is the first winner, the second name is the second, and so on. Because every ordering is equally likely, every entry has the same chance of landing in every position, and no entry can be picked twice for the same giveaway unless it appears on the list more than once.

A browser-based comment picker such as this one follows exactly this pattern, using a secure random source and a Fisher-Yates shuffle, and everything happens on the device rather than on a server. The algorithm can only be fair to the list it is given, though. Duplicates, bots and missing entries are matters for your giveaway rules and for the way you prepare the list, not for the shuffle itself.

What a fair shuffle does not do

An unbiased shuffle guarantees equal treatment of the items in the list. It does not check that the list is complete, that entrants were eligible, or that the rules were followed. It also cannot make a result look convincing to people who were not watching, so some organisers record the draw or share a screenshot of the finished order.

Understanding the method helps you answer the most common question after a draw: “how do I know it was random?” The honest answer is that a properly implemented Fisher-Yates shuffle with a secure random source treats every ordering as equally likely, and that the remaining fairness questions belong to how you ran the giveaway around it.