MSのブラウザ選択のバグに関する説明が、全くわかってない人が書いてるとしか思えない内容だったので javascript の sort について少し解説をしようと思う。

MS、Webブラウザ選択画面にアルゴリズム上のバグか － ＠IT

JavaScriptの配列の並べ替え（sort）は比較関数を渡すことで柔軟な並べ替えが行える。ここではMath.rand()で半々の確率で正負の値を返しているので、隣り合う要素の並べ替えはランダムに起こる。これで結果もランダムになるように思えるが、実際に意味のある並べ替えを行うためには、並べ替えた後の配列が一定の基準に従っている並べられていることが不可欠で、例えば「a＞b」であれば「b＜a」、「a＜bかつb＜c」であれば「a＜c」でなければならない。これは、隣り合う要素同士をただランダムに入れ替えるだけでは達成できないのだという。

この「並べ替えた後の配列が一定の基準に従っている並べられていることが不可欠」という意味の分からない部分はおそらく下記を訳した物と思われる。

Doing the Microsoft Shuffle: Algorithm Fail in Browser Ballot

Sorting requires a self-consistent definition of ordering. The following assertions must be true if sorting is to make any sense at all:

だから正しい訳は「並べかえには首尾一貫した”大小の定義”が必要である。」になる。

実際にどのようなバグがあったかを説明するにはコードで示すのが一番わかりやすいので直接書いていこう。 問題の、 javascript の sort関数では引数に比較関数を取れる。例えば

function comp(a, b){ return a < b; //降順で並べる } function sortnum(){ return [0,3,5,6,-6].sort(comp); } //=>6,5,3,0,-6
function comp(a, b){ return a < b; //昇順で並べる } function sortnum(){ return [0,3,5,6,-6].sort(comp); } //=>-6,0,3,5,6

このように「どういう基準で並び替えを行うかをユーザー自身が関数で定義できるようになっている。ところが問題のコードは恐ろしいことに、この比較関数に以下のような同じ引数でも呼び出しごとに返り値が異なる書き方をしてしまっていたらしい。

return (0.5 - Math.random());

これじゃ sort 関数ががんばって並び替えを行なってる最中に「昇順で並べてね」という命令と「降順で並べてね」という命令が錯綜して与えられる事になる。 そりゃ動くはずもないよ、というわけだ。