Shuffle an Array (Fisher-Yates)
The naive `array.sort(() => Math.random() - 0.5)` looks fine until you measure it: the distribution is heavily biased and some pairs swap with much higher probability than others. The Fisher-Yates shuffle is the standard correct answer in O(n) time with uniform output. This snippet shows the in-place version, a non-mutating wrapper, and an empirical demo of why the popular `sort`-based trick is biased.
1,068 views
7
function shuffle(array) {
for (let i = array.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[array[i], array[j]] = [array[j], array[i]];
}
return array;
}
const deck = [1, 2, 3, 4, 5];
shuffle(deck);
console.log(deck.length === 5);
console.log([...deck].sort((a, b) => a - b));
// [1, 2, 3, 4, 5] (same elements, scrambled order)The Fisher-Yates shuffle walks the array from the end and at each position picks a random index in [0, i], then swaps. The crucial detail is that the random range shrinks each step (i + 1), which is what gives every permutation an equal probability. Anything that picks from [0, length) for every iteration produces a biased distribution. The algorithm is O(n) time, O(1) extra space, and is the textbook correct shuffle. We verify by sorting a copy and confirming the original elements are preserved.
function shuffled(array) {
const copy = array.slice();
for (let i = copy.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[copy[i], copy[j]] = [copy[j], copy[i]];
}
return copy;
}
const original = ['a', 'b', 'c', 'd'];
const rolled = shuffled(original);
console.log(original); // ['a', 'b', 'c', 'd'] (unchanged)
console.log(rolled.length === original.length);Mutating helpers are convenient inside hot loops but a sharp edge in functional code, React state, and immutable contexts. shuffled(array) does a single slice() to clone, then runs the same Fisher-Yates on the copy, so the caller's array is left alone. The cost is one extra O(n) allocation, which is almost always negligible. Use the non-mutating version by default in UI code (e.g. randomising a quiz order) and reserve the in-place form for tight loops where you control the lifetime of the array.
function biasedShuffle(array) {
return array.slice().sort(() => Math.random() - 0.5);
}
// Run many trials and count how often each element ends up at index 0.
const counts = { a: 0, b: 0, c: 0 };
const trials = 30000;
for (let t = 0; t < trials; t++) {
const result = biasedShuffle(['a', 'b', 'c']);
counts[result[0]]++;
}
console.log(counts);
// Roughly: { a: ~14000, b: ~9000, c: ~7000 }, far from uniform.
// A correct Fisher-Yates would give each ~10000.The single most common shuffle bug on the internet is array.sort(() => Math.random() - 0.5). It looks elegant, but Array.prototype.sort is allowed to call the comparator a non-uniform number of times per pair, and an inconsistent comparator (one that does not encode a real total order) yields a biased permutation. Running 30,000 trials shows the elements landing at index 0 with very different frequencies, far from the ~10000 each a uniform shuffle would produce. Stick to Fisher-Yates from the previous accordions, and reach for crypto.getRandomValues if the use case (security tokens, raffle picks) demands a cryptographically strong source. The takeaway is that sort is not a randomiser even when its comparator looks random.