JavaScript の sort は正しく使わないとブラウザによって挙動が変わるという話

はじめに

JavaScript には Array.prototype.sort() という配列を並べ替えるためのメソッドがあり、このメソッドは、引数に比較関数を渡すことでソートの仕方をカスタマイズすることができます。しかし、この比較関数は正しく使わないとブラウザによって挙動が異なってしまうことがあります。私はこの違いに気づかず時間を費やしてしまったので、今回は、その概要とブラウザ間の具体的な挙動の違いについてお話ししたいと思います。

通常の Array.prototype.sort(compareFn) の使用例

const compareFn = (a, b) => {
    if (a < b) return -1;
    if (a > b) return 1;
    return 0;
}
["alice", "bob", "carol"].sort(compareFn)

この例は、文字列を昇順でソートする関数です。
sort の引数として渡す関数は、引数を2つとり、Number 型の値を返す必要があり、返す値は、負なら a < b、正なら a > b、0 なら a = b という意味を持ちます。

間違った使い方 (ブラウザによって挙動が変わる例)

const compareFn = (a, b) => a < b
// 文字列を降順でソートする
["alice", "bob", "carol"].sort(compareFn)

なんとなく compareFn が true を返せば a < b、false を返せば a >= b というように上手く解釈されることを期待してしまいますが、実際には型変換により true -> 1, false -> 0 に変換され、意図しない挙動に繋がります。

そして、この例では
Firefox の場合:

>> ["alice", "bob", "carol"].sort((a, b)=> a < b)
<- Array(3) [ "carol", "bob", "alice" ] // 期待通り (降順)

Chrome の場合:

>> ["alice", "bob", "carol"].sort((a,b)=> a < b)
<- Array(3) [ "alice", "bob", "carol" ] // 期待通りでない

というように、ブラウザによって挙動が異なることがあります。なぜこのような違いが生じるのでしょうか

ブラウザによって異なる挙動を観察してみる

ここで、sort() に渡す関数を

(a, b) => {
    console.log(`${a} と ${b} を比較`);
    return a < b
}

として、ブラウザごとにどのような比較が行なわれているのかを見てみます。

Firefox の出力

alice と bob を比較
alice と carol を比較
bob と carol を比較

Chrome の出力

bob と alice を比較
carol と bob を比較

どちらのブラウザも初めは一番最初の要素同士を比較しているようですが、Firefox では a が b より小さいかどうかを比較しているのに対し、Chrome では b が a より小さいかどうかを比較していることが見てとれます。

ブラウザの実装の違い

次に、各ブラウザの実装から違いを探ります。
Firefox の実際のソースコードでは、
Array.prototype.sort の定義から最終的に呼び出されていると思しき関数 ArraySortResult ArraySortData::sortWithComparatorShared(ArraySortData* d) https://searchfox.org/mozilla-central/source/js/src/builtin/Sorting-inl.h#139 を参照すると、現在の Firefox では、sort() する配列の長さがInsertionSortMaxLen( = 8) 以下のときは挿入ソートを行い、それ以外の場合はマージソートのような処理を行っています。

一方、Getting things sorted in V8 · V8 によると、Chrome では TimSort と呼ばれるより複雑なソートアルゴリズムを用いているようです。

このような比較関数に与える順序の違いや、そもそものソートアルゴリズムの違いが sort() の挙動の違いの原因と考えられます。

(補足) 正しい compareFn を書くためには

これらの実装の違いに左右されない適切な比較関数を書くために比較関数が満たすべき要件として、
MDN web docs では以下のようなものが挙げられています。(1以外については順序集合の性質を満たすための条件です。)

1. 純粋関数であること (副作用があったり、同じ引数に対して異なる結果を返したりすることがないこと)
2. 反射律を満たすこと ($a \leq a$)
3. 反対称律を満たすこと ($a \leq b$ かつ $b \leq a$ ならば $a = b$)
4. 推移律を満たすこと ($a \leq b$ かつ $b \leq c$ ならば $a \leq c$)

そもそも (a, b) -> a < b の例のように f("bob", "alice") = false == 0 となり "alice" == "bob" のように評価してしまう関数は論外ではありますが、関数が上のような性質を持っていることを確認できれば実行環境によらないソートを実現できると思います。

まとめ

Array.prototype.sort() のブラウザ間の挙動や実装の違いを実際に確かめ、どのように正しい compareFn を書くべきかを見てきました。このような違いが生じることを知っておくことで、より安全に sort() を使うことができるでしょう。