単に挿入法や挿入ソート呼ぶ場合や基本挿入法と呼ぶ場合もあります。
単純交換法やバケットソートなどと並び基本的なソートアルゴリズムの1つです。
単純挿入法のアルゴリズム
今回の例では以下の数値の配列をソートしたいものとします。
単純挿入法は単純交換法に少し似ています。違うのは名前の通り挿入を使う点です。
値の大小を比較して、その結果を元に値を挿入していきます。
先ず13と8を比較します。13＞8になりますね。8は13より小さいので13よりも（昇順ソートなら）右にいるべきです。そこで8を13の直前に挿入します。ここでは初回のソートなので先頭になります。ここで8と13はソート済み領域となります。
次にソート済み領域の8と未ソート領域の先頭の18を比較します。8＜18なので挿入は行いません。
次にソート済み領域の13と未ソート領域の先頭の18を比較します。13＜18なので挿入は行いません。
これでソート済み領域に比較対象がなくなったので、18は13の直後に挿入します。（そのままという意味でもOK）
この時点で8 13 18がソート済み領域になりました。
今度は未ソート領域の先頭が45ですので、45を比較していきますが、ソート済み領域のどの値よりも大きいので結果的に45は18の後ろに挿入されることになります。
ここまでで8 13 18 45がソート済み領域になりました。
次は未ソート領域の先頭が11になりましたので、8から順番に比較していきます。
13と比較した時、13＞11となりましたので挿入が発生します。11を13の直前に挿入します。
こうして8 11 13 18 45がソート済み領域になりました。以下処理を続けていくと…
となりソートすることができました。
単純挿入法の利点と欠点
単純交換法やバケットソートなどに並びあまり計算効率は良くないですが、簡単で実装が容易です。そのため使い所を見極められれば有用なアルゴリズムだと言えます。
また単純挿入法は安定ソートです。
