挿入ソートとは、配列Aのx番目の追加要素aをxから先頭に向かって比較し、挿入位置を特定する方法。

■実装

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

// sort
for(var i = 1; i < ary.length; i++){
    var val = ary[i];
    for(var i2 = i - 1; i2 >= 0; i2--){
        if(ary[i2] > val){
            ary[i2 + 1] = ary[i2];
        }
        else{
            break;
        }
    }
    ary[i2 + 1] = val;
}

console.log(ary);

■特性

• 最初から集団がほぼ整列しているような場合に適している
• ランダムなデータに対しては効率が悪い
• 計算量が最小となるのは集団が完全に整列していた場合でO(n)である
• 計算量が最大となるのは集団が完全に逆順だった場合でO(n ^ 2)である
• 平均時性能はO(n ^ 2)である。