整列アルゴリズムのひとつ。
単純挿入法とも呼ばれ、安定な整列法である。実行時間はO(n^2)であるが、ほぼ整列しているデータに対しては非常に早い。

プログラミング掲示板「ソートロジック大会」なども参照のこと

TypeDef keytype = Integer
Sub insertsort(n As Integer, a As *keytype)
Dim i As Integer, j As Integer
Dim x As keytype
For i = 1 To n
'整列の比較要素を定める
x = a[i]
'xよりも大きいものを右に寄せる
j = i - 1
While j >= 0 And a[j] > x
a[j + 1] = a[j]
j = j - 1
Wend
a[j + 1] = x
Next i
End Sub