InsertionSort(挿入ソート:基本挿入法)

ソート済みの列に対し,未整列データをひとつずつ挿入していく.
配列は挿入が苦手なため,リスト構造などを用いて実現することが多い.
5 4 3 6 2が入力された場合,先頭の5がソート済み列であるとして,

4 5 3 6 2 # 4を5の前へ挿入,4 5 がソート済み列
3 4 5 6 2 # 3を4の前へ挿入,3 4 5 がソート済み列
3 4 5 6 2 # 6を5の後ろへ挿入,3 4 5 6 がソート済み列
2 3 4 5 6 # 2を3の前へ挿入,2 3 4 5 6 がソート済み列

となる.