归并排序(Merge Sort):将多个有序数组进行合并。例如待排序数据为6、8、4、2、9、6、1、3、7；
一般最常见的是两路归并，将两个有序数组进行合并，还有三路、五路归并，但是他们的核心思想都是一样的，问题是哪里存在我们需要的有序数组？
我们将待排序数据分成两组(6、8、4、2、9为1组，6、1、3、7为1组)，使之分别有序，在进行合并。那么我们又如何让分成的两组数据变的有序呢？同样的方法将分完的两组数据在进行分组(6、8、4为1组2、9为1组)有序之后在进行合并；(6、8为1组，4为1组)有序之后在进行合并；(6为1组，8为1组)，就是将一组数据的分成左右两组分别处理有序，在进行合并，最下面，左边一个数据6有序，右边一个数据8有序，两组都不需要进行处理，合并6和8，6比8小，6在前边，左面这组向右移动，没有数据了，8放在后面。左边，6，8有序，右边一个数据4有序，合并，6和4比，6比4大，4在前面，4再向后，没有数据了，合并结果4、6、8；右半部分分成两组2、9，左边一个数据2有序，右边一个数据9有序，2和9比，2比9小，2在前面，2向后走，没有数据了，右半部分合并完成2、9；（现在要合并的两组分别是4、6、8和2、9），同样遍历比较，4和2比，4比2大，2放前边，2向后走，4比9小，4放前边，4向后走，6比9小，6放前边，6向后走，8比9小，8放前边，8后面没有数据了，那么9后面剩多少数据连同9一起放在8的后面，左半部分处理完成2、4、6、8、9；接下来看整体的右部分，(6、1为1组，3、7为1组)，然后再分组（6为1组，1为1组），(3为1组，7为1组)；左右两边都是一个数据，有序，6和1比，6比1大，1在前边，1向后走，没有数据了，6在1后面，左组1、6有序，右组的左右两边都是一个数据有序，3和7比，3比7小，3在前边，3向后走，没有数据，7放在3后，3、7有序，(现在要合并的两组分别是1、6和3、7)，1和3比，1比3小，1放前边，1向后走，6比3大，3放前边，3向后走，6比7小，6放前边，6向后走，没有数据了，7放在6后面，合并完成1、3、6、7；现在要合并的两组为（2、4、6、8、9和1、3、6、7）也都是同样道理，2和1比，2比1大，1放前边，1向后走，2比3小，2放前边，2向后走，4比3大，3放前边，3向后走，6比4大，4放前边，4向后走，6和6比，都一样，就当左边的6小，6放前边，6向后走，8和6比，6比8小，6放前边，6向后走，8和7比，8比7大，7放前边，7向后走，没有数据了，8连同8后面的数据都放在7后面，合并完成，结果为1、2、3、4、6、6、7、8、9。
一句话概括归并排序就是先分割，在合并，合并两个数组与合并链表一样，都从头开始遍历，谁小谁放在前边。
#include<stdio.h>#include<stdlib.h>//归并排序void Merge(int arr[],int nBegin,int nEnd){int nBegin1 = nBegin;int nEnd1 = nBegin +(nEnd-nBegin)/2;int nBegin2 = nEnd1+1;int nEnd2 = nEnd;int *pTemp = NULL;pTemp = (int *)malloc(sizeof(int)*(nEnd-nBegin+1));int i = 0;while(nBegin1 <= nEnd1 && nBegin2 <=nEnd2){if(arr[nBegin1]<arr[nBegin2]){pTemp[i] = arr[nBegin1];i++;nBegin1++;}else{pTemp[i] = arr[nBegin2];i++;nBegin2++;}}//将剩余的数组元素继续放入while(nBegin1 <= nEnd1){pTemp[i] = arr[nBegin1];i++;nBegin1++;}while(nBegin2 <= nEnd2){pTemp[i] = arr[nBegin2];i++;nBegin2++;}//放回for(i = 0;i<nEnd-nBegin+1;i++){arr[nBegin +i] = pTemp[i];}//释放free(pTemp);pTemp = NULL;}void MergeSort(int arr[],int nBegin,int nEnd){if(arr == NULL || nBegin>=nEnd) return;//分割int nMind = nBegin +(nEnd -nBegin)/2;MergeSort(arr,nBegin,nMind);MergeSort(arr,nMind+1,nEnd);//合并Merge(arr,nBegin,nEnd);}void Printf(int arr[],int nlength){if(arr == NULL||nlength<=0) return;int i;for(i=0;i<nlength;i++){printf("%d ",arr[i]);}}int main(){int arr[]={10,2,11,4,56};MergeSort(arr,0,sizeof(arr)/sizeof(arr[0])-1);Printf(arr,sizeof(arr)/sizeof(arr[0]));printf("n");return 0;}