JavaScript shuffle idea

Question

Based on the standard implementation of Array.sort in JavaScript, would the following be a reasonable way of shuffling the contents of an array? Is it moderately efficient and will it produce a fairly even spread of results?

Array.prototype.shuffle = function () {
 return this.sort(function(){ return Math.random() - 0.5;});
};

Answer 1

This article says that a test run on that algorithm showed a bias with items less likely to move farther away from their original location than near (a bias).

My own intuition says that it could cause issues because the .sort() algorithm expects that when a given two elements are compared they will always have the same comparison result and yet that is not true when using this function. Therefore, I'm thinking that how well this work could also depend upon how the .sort() method was actually implemented internally.

This article shows what seems to me like a better algorithm for randomness, though I wouldn't expect it to be particularly efficient:

Array.prototype.shuffle = function() {
 var s = [];
 while (this.length) s.push(this.splice(Math.random() * this.length, 1));
 while (s.length) this.push(s.pop());
 return this;
}

EDIT: Also just found this same question here: https://stackoverflow.com/questions/962802/is-it-correct-to-use-javascript-array-sort-method-for-shuffling. That answer suggests this which is based on the Fisher-Yates algorithm and would be a lot more efficient than the algorithm above:

function shuffle(array) {
 var tmp, current, top = array.length;
 if(top) while(--top) {
 current = Math.floor(Math.random() * (top + 1));
 tmp = array[current];
 array[current] = array[top];
 array[top] = tmp;
 }
 return array;
}

And, here's a testpage that shows the results of your proposed method vs. the Fisher-Yates method in your browser: http://phrogz.net/JS/JavaScript_Random_Array_Sort.html.

• Cory Dolphin: +1 on Fisher-Yates as a common and efficient algorithm for shuffling that is used in many places. You can read more about the algorithm en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle