How to properly shuffle a list in javascript

[dtm]

Because I've recently read an article on how Microsoft has egg on its face because of this, and because searching on Google for "sort a list randomly in javascript" currently shows the wrong thing to do in the top several hits, here's how to take a list in javascript and shuffle it, or sort it in a truly random order.

Also, yeah, it's been over two months since I last posted, etc.

However, this is just going to be code, and anyone who still has me in the old friends list probably doesn't need their livejournal covered with code, so it goes behind a cut...

I guess I should say first that this isn't just a problem that affects javascript - many languages have a sort function that takes an arbitrary comparison function, and it seems natural to sort in "random" order by using a comparison function that chooses its return value randomly.

Don't do this. If you do, your code won't be producing a fair shuffle. This is how Microsoft's browser choice website wound up broken.

Instead, there are two simple methods that shuffle easily and fairly: sorting by random key (random key, not random comparison function), and the Fisher-Yates shuffle. I'm doing the second because it's easier to demonstrate in javascript; the first is easier in some language like Python where it's just
list.sort(key=random.random)

So here's the code. See how short it is?

//shuffles list in-place
function shuffle(list) {
  var i, j, t;
  for (i = 1; i < list.length; i++) {
    j = Math.floor(Math.random()*(1+i));  // choose j in [0..i]
    if (j != i) {
      t = list[i];                        // swap list[i] and list[j]
      list[i] = list[j];
      list[j] = t;
    }
  }
}

Okay? Now, I don't want to see anyone else write an article or respond to a mailing list question about how to "sort a list randomly" with incorrect advice about using sort with a random comparison function. It just doesn't work.

(Of course, if your language already provides a good shuffle library function, use that in preference to reinventing the wheel. If you're using Java, look at Collections.shuffle. In Python, look at random.shuffle. In Perl, List::Util::shuffle.)