TimSort in JSX - Islands in the byte stream (legacy)

JavaScriptのArray.prototype.sort()のアルゴリズムは特に規定されていないようだ。つまり、stableかどうかや最悪計算量は処理系依存である。その結果、JSXのsort()も同様となっている。 そこで、stable sortであるTimSortのJava版をJSXに移植してみた。 https://github.com/gfx/jsx-stable-sort/ このアルゴリズムは、完全にランダムシャッフルされた配列に対してはmerge-sortやquick-sortよりも時間が掛かる傾向にある。しかし、一部がsort済みである配列に対しては非常に速い。 nodejs 0.8.0 (MacOSX Lion)で100万要素の配列をソートする時間を測ってみた。組み込みsortはソートされた配列を返す非破壊的ソートで、StableSortの非破壊版は完全にシャッフルされた

[gfx]

blogged