Unfortunately there is no simple "one liner" that will shuffle an array in javascript. All to often I see people advising to use:

sort(function() { Math.random() - 0.5 }))

However, this does not shuffle the array. First, let's take a look at what does work. It's called the Fisher-Yates shuffle and looks like this in javascript:

function shuffleSort(a) { for(var i = 0; i < a.length; i++) { var r = Math.floor(Math.random() * (i + 1)); var t = a[i]; a[i] = a[r]; a[r] = t; } }

Why doesn't sorting with a random comparator work? It all depends on the algorithm and what I found really interesting is how each sort algorithm has a different "order bias" which can be made into an image by mapping original position on the `x`

and final position on the `y`

and shading the probability from `0.0`

cyan and max percent magenta. Also, in the images below I've expanded the image size so each original-final is 2x2 pixels and they are seperated by white space. Each test was run on an array initialized to `[0..99]`

sorted and run for 1 million iterations. If you want to play around with the code it's all here and an example page with images here.

# Fisher-Yates shuffle

function shuffle(a) { for(var i = 0; i < a.length; i++) { var r = Math.floor(Math.random() * (i + 1)); var t = a[i]; a[i] = a[r]; a[r] = t; } }

As expected this produces a pretty flat image with a probability range `[0.009627, 0.010367]`

after 1 million iterations.

# Random Sort

function randomSort(a) { a.sort(function() { return Math.random() - 0.5 }); }

Probability range `[0.000965, 0.033447]`

after 1 million iterations.

# Quick Sort

Probability range `[0.006287, 0.073966]`

after 1 million iterations. Just from the looks of it quick sort seems to have the worst performance in the center of the array getting the least shuffle.

# Bubble Sort

function bubbleSort(a) { var l = a.length; var i, j, s, t; for (i = 0; i < l; i++) { for (j = 0, s = l-i-1; j < s; j++) { if (Math.random() < 0.5) { t = a[j]; a[j] = a[j+1]; a[j+1] = t; } } } }

Probability range `[0 0.500113]`

after 1 million iterations, which is amazing that after that many trials there were still positions that certain numbers never made it to.

At first I thought my sort was off, but then I realized to move `0`

from first position to last position requires the comparator (in this case `Math.random() - 0.5 < 0.0`

) to be less than `0.5`

99 times in a row. Also, for `9`

to remain in last position is `0.5`

percent chance that when `i=0`

and `j=9`

that `Math.random() < 0.5`

is false. I double checked this for arrays size 10 in length and the probability range was as expected `[0.001923 0.500352]`

since `Math.pow(0.5, 9) == 0.001953125`

.

# Selection Sort

function selectionSort(a) { var i, j, m, t; var l = a.length; for (i = 0; i < l; i++) { m = i; for (j = i+1; j < l; j++) { if (Math.random() < 0.5) m = j; } if (i != m) { t = a[i]; a[i] = a[m]; a[m] = t; } } }

Probability range `[0 0.500113]`

after 1 million iterations. Selection sort has some similar problems that bubble sort does. Consider an array `a=[0..9]`

what is the probability that `9`

which started in the last position will end up in the first position? If the array was shuffled it should be `0.1`

, right? But instead for selection sort it is `0.5`

. Because the only way for `9`

to move to the front is when `i=0`

and `j=9`

the comparator (in this case `Math.random() - 0.5 < 0.0`

) is less than zero which happens half the time.

# Insertion Sort

function insertionSort(a) { var l = a.length; var i, j, t; for (i = 0; i < l; i++) { t = a[i]; for (j = i-1; j > -1 && Math.random() < 0.5; j--) { a[j+1] = a[j]; } a[j+1] = t; } }

Probability range `[0 0.499359]`

after 1 million iterations.