· Development

Why sort(() => Math.random() - 0.5) is not a fair shuffle, and what Fisher–Yates does instead

A random comparator doesn't shuffle evenly, and the ECMAScript spec says why. How Fisher–Yates makes every permutation equally likely, and the random-number pitfalls it still depends on.

DevelopmentAlgorithms

Search for how to shuffle an array and this one-liner comes up a lot:

const shuffled = items.sort(() => Math.random() - 0.5);

It is short and looks reasonable, but it does not shuffle evenly. Shuffling ['A', 'B', 'C'] this way 600,000 times and counting each order gives:

Order Share
ABC 37.4%
ACB 6.2%
BAC 12.5%
BCA 6.3%
CAB 6.3%
CBA 31.3%

A fair shuffle would put each of the six orders near 16.7%. These numbers were observed on Node.js v24.13.0, and other engines or versions may give a different distribution. That variation is part of the problem.

The spec doesn’t support this use

The ECMAScript specification defines sort’s ordering guarantees in terms of a “consistent comparator”. The first condition for one is that calling it with the same pair a, b always returns the same value. Math.random() - 0.5 can return a different value, and sometimes a different sign, when called again with the same pair, so it breaks that condition. In that case the spec says only that the sort order is implementation-defined. The resulting distribution depends on which pairs the engine’s sort algorithm compares and how often, and nothing promises it is uniform.

Swapping with any position is biased too

Hand-written shuffles have a common mistake of their own: at each position i, swap with a position j picked from the whole array.

// biased
for (let i = 0; i < a.length; i++) {
  const j = Math.floor(Math.random() * a.length);
  [a[i], a[j]] = [a[j], a[i]];
}

With three elements there are 3 × 3 × 3 = 27 equally likely choice sequences but only 6 permutations. 27 is not divisible by 6, so the permutations cannot come out equally often. Tracing all 27 shows ABC, CAB and CBA appearing 4 times each and ACB, BAC and BCA 5 times each. In general, for n of 3 or more, n and n−1 share no common factor. So n^n is not divisible by n−1, and therefore not by n! either. This method is always biased once there are three or more elements.

Fisher–Yates: pick only from the cells not yet fixed

A fair shuffle fixes one cell at a time from the end. At position i it swaps with a position chosen from 0 to i, the cells that are not settled yet.

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

There are n × (n−1) × … × 2 = n! choice sequences, and each permutation comes from exactly one of them. If j is uniform over its range, every permutation has probability 1/n!. The loop runs n−1 times, so it is O(n).

Standard libraries use the same structure. The documentation for Java’s Collections.shuffle says it walks the list backwards from the last element to the second, swapping into the current position an element chosen from the first element up to the current position. The source code of CPython’s random.shuffle and Go’s math/rand/v2 Shuffle has the same loop, and a comment in the Go source names it Fisher–Yates.

The algorithm can be right and the randomness still wrong

Fisher–Yates is only as uniform as the j it is given.

  • Range. Math.floor(Math.random() * (i + 1)) yields an integer from 0 up to but not including i + 1, the same range as MDN’s getRandomInt example. Use i instead of i + 1 and j can never equal i. The last cell then always receives a different element, so some permutations, including the original order, never appear.
  • Modulo bias. Reducing a 32-bit random integer with % n favours small values whenever 2^32 is not a multiple of n. 2^32 mod 6 is 4, so 0 to 3 each get one more source value than 4 and 5. To avoid it, reject any value at or above floor(2^32 / n) × n and draw again before applying % n. The values you keep then come in a multiple of n, so every result from 0 to n−1 gets the same number of them. CPython’s _randbelow also redraws: it draws just enough bits and draws again whenever the result is n or more.
  • Security. MDN notes that Math.random() does not provide cryptographically secure random numbers and points to crypto.getRandomValues() for anything security-related. The Python docs likewise point to the secrets module instead of random for security uses. If someone could gain by predicting a draw, change the generator first.
  • Generator period. The Python docs warn that even for fairly short sequences, the number of permutations can exceed the period of most random number generators, so most permutations of a long sequence can never be generated. For the Mersenne Twister (period 2^19937−1), the longest sequence whose permutations all fit within the period is 2080 elements. This is exactly why Java’s documentation says “approximately equal likelihood”: its default source of randomness is only approximately an unbiased source of independent bits.

When you only need a few

If you need k items out of n (0 ≤ k < n), you can stop after k iterations. Shuffling from the end, the last k cells are then a random sample. For k = n, run the full n−1 iterations as in the function above. In Python, random.sample(population, k) makes k selections without replacement and returns them in selection order, leaving the original unchanged. If the population contains repeated values, the same value can appear more than once in the result.

The random name picker and team generator on this site also shuffles with Fisher–Yates. It picks j from 32-bit crypto.getRandomValues() values, rejecting any at or above floor(2^32 / n) × n and drawing again.

Back to the blog