Why isn't this shuffle algorithm biased

Question

My coworker and I are arguing about why the shuffle algorithm given in this list of JS tips & tricks doesn't produce biased results like the sort Jeff Atwood describes for naive shuffles.

The array shuffle code in the tips is:

list.sort(function() Math.random() - 0.5);

Jeff's naive shuffle code is:

for (int i = 0; i < cards.Length; i++)
{
  int n = rand.Next(cards.Length);
  Swap(ref cards[i], ref cards[n]);
}

I wrote this JS to test the shuffle:

var list = [1,2,3];
var result = {123:0,132:0,321:0,213:0,231:0,312:0};
function shuffle() { return Math.random() - 0.5; }
for (var i=0; i<60000000; i++) {
    result[ list.sort(shuffle).join('') ]++;
}

For which I get results (from Firefox 5) like:

Order   Count          %Diff True Avg
123      9997461       -0.0002539
132     10003451        0.0003451
213     10001507        0.0001507
231      9997563       -0.0002437
312      9995658       -0.0004342
321     10004360        0.000436

Presumably Array.sort is walking the list array and performing swaps of (adjacent) elements similar to Jeff's example. So why don't the results look biased?

Answer 1

I found the reason it appears unbiased.

Array.sort() not only returns the array, it changes the array itself. If we re-initialize the array for each loop, we get results like:

123 14941
132 7530
321 7377
213 15189
231 7455
312 7508

Which shows a very significant bias.

For those interested, here's the modified code:

var result = {123:0,132:0,321:0,213:0,231:0,312:0};
var iterations = 60000;
function shuffle() { 
    comparisons++;
    return Math.random() - 0.5;
}
for (var i=0; i<iterations; i++) {
    var list = [1,2,3];
    result[ list.sort(shuffle).join('') ]++;
}
console.log(result);