Description

The current shuffle function used by the bogoSort implementation appears to implement a biased version of the Fisher–Yates shuffle.

Specifically, the random index is selected from an incorrect range, which prevents some permutations from ever occurring. This results in a non-uniform shuffle and may affect the theoretical correctness of randomized algorithms such as bogoSort.

Expected Behavior

The shuffle function should implement an unbiased Fisher–Yates algorithm, where each permutation of the array is equally likely.

This requires selecting the random index from the inclusive range [0, i] during each iteration.

Actual Behavior

The current implementation selects the random index from [0, i), which introduces bias and makes some permutations impossible.

As a result:

• The shuffle is not uniform
• The sorted permutation may be unreachable for certain inputs
• The expected probabilistic behaviour of bogoSort is violated

Steps to reproduce (if applicable)

1. Use the current shuffle implementation
2. Shuffle a small array (e.g. [1, 2, 3]) many times
3. Count permutation frequencies
4. Observe that some permutations never appear or appear significantly less often

Additional information

Suggested fix

Update the shuffle to use the standard Fisher–Yates algorithm:

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]];
 }
}