插入排序

像排序一手扑克牌，开始时左手为空，桌面上牌堆朝下。然后，我们每次从桌子上拿一张牌，并插到左手中正确的位置。左手的牌总是排序好的。

伪代码

INSERTION-SORT(A)

for j=2 to A.length

key = A[j] // A[j]表示当前抓的牌

i = j-1

while i>0 and key[InvalidCharacterError: "A[I]<" did not match the Name production]

一般来说，算法需要的时间与输入规模同步增长。

对某些算法，平均情况往往和最坏情况一样差，并且最坏情况经常出现。