■実装
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)