Array#sortはオレmergesortよりも遅い!?

前のエントリのトラックバックが相手方になぜか反映されないのですが、言及していただけました。

404 Blog Not Found:perl - the sort pragma
「マージソートだから遅いわけじゃない」ってことが書いてありました*1。なるほど。

せっかくなので、マージソートもJavaScriptで作ってみました。

var msort  = function(ary, cmp) {

  var aux = new Array(ary.length);

  for(var i=0,n=ary.length;i<n;i++) {

    aux[i] = ary[i];

  }    

  function m(src, dest, low, high, cmp) {

    var len = high - low;

    if(len <= 1) {

      return;

    }

    else {

      var mid = (high + low) >> 1;

      m(dest, src, low, mid, cmp);

      m(dest, src, mid, high, cmp);

      

      var p = low;

      var q = mid;

      for(var i=low;i<high;i++) {

        if(q >= high || (p < mid && cmp(src[p], src[q]) <= 0)) {

          dest[i] = src[p++];

        }

        else {

          dest[i] = src[q++];

        }

      }

    }

  }

 

  m(aux, ary, 0, n, cmp);

  return ary;

};

これを404 Blog Not Found:javascript - Array#sortがオレquicksortより遅い!?の「検証ソース一式」に組み込んで試してみると･･･

# Firefox2.0の場合
Sorting Random Array with 10000 items.
Builtin: 1531ms
Quicksort: 1594ms
Mergesort: 1172ms

# IE6.0の場合
Sorting Random Array with 10000 items.
Builtin: 1422ms
Quicksort: 1672ms
Mergesort: 1406ms

Firefoxではオレmergesortが一番速いという結果に（汗

というわけで、前言はきれいさっぱりと撤回させていただきます。

*1:編集ミスだと思うのですが、19:30現在では、冒頭の引用箇所以降が前の記事と同じなっています。⇒再修正されました。