TimSort in JSX

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の非破壊版は完全にシャッフルされた配列に対してはやや遅い。しかしシャッフルする要素の量が1/4ほどだと組み込み版よりかなり速くなる。破壊的変更を行う版(StableSort!)は、完全にシャッフルされていても組み込み版とほぼ同じで、ソートする量が少なければ圧倒的に速い。これなら実用になりそうだ。

->> make benchmark 
jsx --release --run stable-sort.jsx
shuffled 0..1000000
StableSort!:  384[ms]
StableSort:   525[ms]
builtin sort: 375[ms]
shuffled 0..500000
StableSort!:  240[ms]
StableSort:   463[ms]
builtin sort: 460[ms]
shuffled 0..250000
StableSort!:  135[ms]
StableSort:   261[ms]
builtin sort: 408[ms]
shuffled 0..125000
StableSort!:  78[ms]
StableSort:   208[ms]
builtin sort: 363[ms]
shuffled 0..62500
StableSort!:  41[ms]
StableSort:   166[ms]
builtin sort: 442[ms]