什么是归并排序？
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
步骤如图：
那我们要如何实现呢？
1. 递归法代码如下：
// 归并排序
//合并两个有序数组
void Sort(int*a,int left,int mid,int right){
int*p=(int*)malloc(sizeof(int)*(right-left+1)); //开辟一个大小是right-left+1的空间
int p1=left;
int p2=mid+1;
int p3=0;
while(p1<=mid&&p2<=right){
if(a[p1]=right){ //当数组只有一个元素，可以看做有序的
return;
}
mid=(left+right)/2;
MergeSort(a,left,mid); //排序左半数组
MergeSort(a,mid+1,right); //排序右半数组
Sort(a,left,mid,right); //合并两个有序数组
}
这样我们就完成了归并排序的递归版本
2. 非递归版从图中我们可以看出，最终先合并的是元素个数只剩一个的数组两两合并，那我们使用非递归就可以先实现最后这一步：
//非递归写法
void MergeSort2(int*a,int n){
int*tmp = (int*)malloc(sizeof(int)*n);
int gap=1;//类似于直接先进行递归方式的最后步骤
while(gap
我们将开始数组的大小由1个开始，两两进行归并，最终完成递归的操作，那这样就结束了吗？
我们来看一下每一次归并的数组：
我们这里传入的只是9个元素大小的数组，你怎么给我越界这么多次.
那我们应该怎么去修改它，使它无法越界呢？
这里我们需要重新调整我们的区间：
int start1=i,end1=i+gap-1; //第一个区间
int start2=gap+i,end2=2*gap+i-1; //第二个区间
这是我们之前定义的区间，由上图我们也可以看到除了start1是个好孩子没有越过界，其他都犯了越界，那我们就应该对它们进行批评改正。
这里我们需要考虑三种情况：
1. 如果end1越界
2. 如果end2越界
3. 如果start2越界
修改操作如下：
if(end1>=n){
end1=n-1;
}
if(start2>=n){
start2=n;
end2=n-1;
}
if(start2=n){
end2=n-1;
}
这样我们就可以很好的实现我们的操作
