话不多说，直接上c++代码
int a[7] = { 7,8,1,5,4,21,3 };
int i, j;
for (i = 1; i < 7; i++)
{
int key = a[i];
j = i - 1;
while (j >= 0 && a[j] > key) //改变a[j]
我们可以发现每次循环开始，a[0]到a[i-1]都已经排序完成。我们把它称为循环不变式，性质如下：
（1）、初始化：循环的第一次迭代之前，它为真
（2）、保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍未真
（3）、终止：在循环终止时，不变式为我们提供一个有用的性质，有助于帮我们证明算法是正确的
这类似于数学归纳法（为了证明某条性质，需要证明一个基本情况和归纳步），也就是这样保持了数组的有序性
二、并归排序
分治法思想：将原问题分解为几个规模较小但类似于原问题的子问题；递归地求解这些子问题；然后再合并这些子问题的解来建立原问题的解。这也就是分治模式每层递归时的三个步骤
void Merge(int a[], int l, int mid, int r)
{
int i, j, k;
int n = mid - l + 1, m = r - mid;
int L[50], R[50];
for (i = 0; i
下面是一个叫递归树的东西，高度logn层，每层n个，时间复杂度nlogn
