クイックソートよりも遅いマージソートな理由
404 Blog Not Found:javascript - Array#sortがオレquicksortより遅い!?について
コメントしようと思ったけどちょっと長くなったのでTrackbackに。
コメントには"Perl-inspired"とあって使っているのはmerge sortなのだけど、なぜこんなに遅いのか、これだけじゃまだわからないなあ。
遅いのはマージソートだからでいいのでは？ (注：これは間違でした。次のエントリも参照してください。)
計算量で言えばクイックソートもマージソートも同じO(nlog(n))ですが、現実的にはクイックソートの方が高速だと思います。例のAppletのデモでも見るからにクイックソートの方が速いですし。
では、なぜ遅いマージソートを使うのか。
同じくマージソートを採用している*1javaではjavadocに以下の記載があります。
このソートは固定であることが保証されています。つまり、ソートを実行しても、同等の要素の順序は変わりません。
つまり、これが重要なのではないかと。
例えば、生徒の(名前,性別)オブジェクトのリストがあるとき、名前順でソートした後に性別でソートすれば、男女別の名前順リストが得られます。クイックソートでは、このようにはなりません。
コードで示すと以下のようになります。
function Person(name,sex) {このような性質をもったソートを安定ソートというようです。
this.name = name;
this.sex = sex;
}
Person.prototype.toString = function() {
return "(" + this.name + ":" + this.sex +")";
}
var x = [new Person("やまだ","男"),
new Person("すずき","女"),
new Person("よしだ","男"),
new Person("きむら","女"),
new Person("さとう","男")];
alert(
x.sort(function(a,b){return a.name < b.name ? -1 :
a.name > b.name ? 1 : 0;})
.sort(function(a,b){return a.sex < b.sex ? -1 :
a.sex > b.sex ? 1 : 0;}));
// (きむら:女),(すずき:女),(さとう:男),(やまだ:男),(よしだ:男) と表示される。
ちなみにWindowsのエクスプローラでも、更新日時順にソートした後で、種類順にソートすると ORDER BY 種類, 更新日時のようになります。クイックソートを使ってこのような動作をさせるためには、ユーザが前にどのキーを使ってソートしたかをアプリケーションは記憶しておかなければなりません。やっぱりそれはメンドイのでマージソートの方がうれしいと思います。
これでもし、自前で実装したマージソートが組み込みよりも遅かったら話は別になってしまいますが･･･。
追記
2006-11-23 - 飲み物だから太らない
安定なクイックソート実装もあるそうです。
でも、はてなキーワードでも、Wikipediaでもクイックソートは安定じゃないって書かれているところを見ると、一般的な(認識/実装)としては安定じゃないでいいのかなーと思います。
