插入排序的基本思想是每次取右边的第一个元素，将它与左边已经排好序的元素一一比较，如果该元素比第j个元素大，就将该元素插入到第j和第j+1个元素之间。
最坏的情况下（比如输入序列是个逆序），每个元素都需要跟左边已经排好序的所有元素比较，总的比较次数为：1+2+...+(n-2)=(n-1)(n-2)/2 ~ O(n^2); 插入操作需要将插入位置右边的元素平移一个位置，总得移动操作次数也为O(n^2)。
插入排序是稳定的(stable),这与选择排序不同（选择排序用的是交换非相邻元素位置，所以不稳定），并且如果原序列基本上排好序的情况下，比较和移动操作的次数可以大大降低，因为它只需比较一部分元素，在这种情况下，它与冒泡排序和选择排序不同在于： 冒泡排序需要依次比较元素直到最右端，即使左边的元素已经全部排好序也要依次比较；选择排序也需要查找右边最小的元素，即使有右边的元素已经排好序也要逐个比较。插入排序的这个特性可以用被别的排序算法（比如quicksort）利用。
选择排序优于插入排序的地方可能就是前者的交换操作（即写操作）平均复杂度是O(n)，而后者是O(n^2)，所以在n很大时，想比较而言，选择排序写操作次数非常少。但是选择排序的缺点是不稳定(unstable)。
冒泡排序的写操作是O(n^2)，比较操作在任何情况下（除非左边已经排好序，提前退出）都是O(n^2)，效率极低。
总而言之，插入排序是三个复杂度为O(n^2)的排序算法（插入排序，选择排序和冒泡排序）中比较优的。
以下是该算法的一个实现。在代码中变量j之所以放在外面，是因为语句A[j+1] = tmp;不能放在语句break；之前位置，因为像输入序列为逆序时，比如(2,1)，整个内层循环执行完，而没有执行到break语句。
测试：
1 2
1 2 3 4 5 7 8 9 10 11 19 20