JavaScriptでマージソート

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

JavaScriptでマージソート

以前、JavaScriptでクイックソートを書いてみたことがあったが、今度はマージソートを書いてみた。

var sort = function self(list) {
    if (list.length < 2) return list;
    var left = self(list.splice(0, list.length >>> 1)), right = self(list.splice(0));
    while (left.length && right.length)
        list.push(left[0] <= right[0] ? left.shift() : right.shift());
    return list.concat(left, right);
};

比較関数を使う場合は↓

var sort = function(list, comparer) {
    if (!comparer) comparer = function(x, y) { return x - yy - x; };
    return (function self(list) {
        if (list.length < 2) return list;
        var left = self(list.splice(0, list.length >>> 1)), right = self(list.splice(0));
        while (left.length && right.length)
            list.push(comparer(left[0], right[0]) <>= 0 ? left.shift() : right.shift());
        return list.concat(left, right);
    })(list);
};

意外とシンプルなんだなー

[追記 (2011-06-29)]

安定ソートになっていなかったので一部ソースを修正。Thanks, id:escape_artist!

[追記 (2011-07-03)]

比較関数の定義がECMAScriptのsort関数と逆になっていたので一部修正。

スポンサーサイト

トラックバック URL

http://liosk.blog103.fc2.com/tb.php/58-d02ad21b

トラックバック

コメント

コメントの投稿

お名前
コメント
編集キー
 
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。