@blog.justoneplanet.info

■実装

var n = 10;
var a = [];
for(var i = 0; i < n; i++){
    a[i] = Math.round(Math.random() * n);
}
array = a.concat();


/**
 * msort
 * @param {Object} ary
 */
var msort = function(ary){
    if(ary.length < 2){
        return ary;
    }
    else{
        var l = msort(ary.splice(0, ary.length >>> 1));// 配列の左半分
        var r = msort(ary.splice(0));// 残りの部分配列
        console.log(l.toString());
        console.log(r.toString());
        // 以下の部分でマージする
        while(!(l.length < 1 && r.length < 1)){
            if(!l[0]){
                ary.push(r.shift());
            }
            else if(!r[0]){
                ary.push(l.shift());
            }
            else if(l[0] < r[0]){// 小さい方をpush
                ary.push(l.shift());
            }
            else{
                ary.push(r.shift());
            }
        }
        console.log(ary.toString());
        console.log('===============');
        return ary.concat(l, r);
    }
}


msort(a);
console.log("before : " + array.toString());
console.log("after  : " + a.toString());

■特性

• 最悪時の計算量はO(n log n)
• 安定ソート
• 平均時性能はO(n log n)