插入排序

插入排序从一个元素开始，把已经处理的前缀维持为有序序列。处理下一个元素时，先记住它，再把前缀中比它大的元素向后移动，为它腾出正确位置；重复这一过程直到所有元素都被纳入。

前缀有序是理解算法的关键不变量。一次插入前，前面的元素已经相互排好；移动只是给新元素让位，不破坏它们之间的次序。插入结束后，新前缀仍然有序，因此逐步推进最终能得到完整排序。

参考：[1]

一对元素的先后次序与目标顺序相反，称为一个逆序。采用相邻交换的插入排序，每次交换消除一个逆序，交换总数正好等于原来的逆序数；比较次数还包括检查停止位置的工作。

反向排列的互异键含有二次方数量级的逆序，因此最坏时间为O(n²)。已经有序时，每个新元素很快通过检查，通常的实现只需线性工作。这个差别来自实际输入结构，不是所有排序算法都能同样利用已有次序。

参考：[2] [1]

若只移动严格大于新键的元素，遇到相等键就停下，较晚输入的同键记录便不会越过较早记录，算法因此保持稳定。数组实现还可只保存少量临时变量，不需要另一份与输入等长的后备数组。

这些优点不消除大规模无序输入上的二次方成本。混合排序可以对小子数组改用插入排序，以减少复杂算法的管理开销；阈值取决于实现和运行环境。比较字符串等非固定成本的键时，还应另外计算每次比较本身的工作。

参考：[2] [3]