归并排序是分治思想的一种应用，把复杂大型的问题切分成若干个小问题，在进行一一解决然后进行合并，最后把复杂的问题解决。 先看一个简单的排序程序，这个程序是对两个有序数组进行合并，合并后的数组依然是有序的数组：
int *merge(const int *arry1,const int *arry2,const int len1,const int len2){ int *result = (int*)malloc(sizeof(int)*(len1+len2)); int *ptr = result; int i,j; i = 0; j = 0; while(i<len1&&j<len2){ if(*a1<*a2){ *ptr++ = *arry1++; i++; } else{ *ptr++ = *arry2++; j++; } } while(i<len1){ *ptr++ = *arry1++; i++; } while(j<len2){ *ptr++ = *arry2++; j++; } return result; }这里合并的方法非常简单，就是对两个数组进行遍历，将较小的元素插入新数组当中，因为a1,a2数组原本就是有序的所以这样合并得到的结果依然是有序的，上述代码是按照从小到大的顺序。 假设两个数组分别是{0,1,2,3}，{1,3,4,5}，那么上述合并过程可以描述如下： >result = {0}, i=1 , j=0 >result = {0,1}, i=1 , j=1 >result = {0,1,1}, i= 2 , j=1 >result = {0,1,1,2},i=3 , j=1 >result = {0,1,1,2,3},i=4 , j=1
此时跳出第一个while循环，然后有j < n2，进入while(j < n2)循环
result = {0,1,1,2,3,3},i=4 , j=2 result = {0,1,1,2,3,3,4},i=4 , j=3 result = {0,1,1,2,3,3,4,5},i=4 , j=4
程序结束，得到一个新的数组 {0,1,1,2,3,3,4,5}。 归并排序就是基于上述算法，利用分治的思想实现的。假设要对8个元素进行归并排序，其归并过程如其归并树所示：
其实归并排序是一个自底向上的过程，例如上图中的8元素数组，其先将数组划分成单元素，然后相邻两个元素进行合并，得到4个新的有序数组，然后继续相邻两个数组进行合并，得到两个新的有序数组，最后再合并得到数组排序后的结果。上图的归并树的每一层的合并过程，不管是多少组数组进行两两合并，其过程也只是遍历一次原数组的全部元素而已，故其时间复杂度为O(n)，而树的高度为lg(n)，所以归并排序的时间复杂度为O(nlg(n))。
void merge_sort(int *arry,const int len){ int *result,i; if(len<=1){ return; } merge_sort(arry,len/2); merge_sort(arry+len/2,len-len/2); result = merge(arry,arry+len/2,len/2,len-len/2); for(i=0;i<len;i++){ *arry++ = *(result+i); } free(result); }由于归并排序是一种变址排序，所以上述代码在归并完成后需要对原数组重新赋值。其实如果没有必要，也可以不这样做，直接返回排序后的数组即可。
本文是转载自http://blog.csdn.net/ivan_zgj/article/details/51446520 只是做了一些描述上的修改。
转载于:https://www.cnblogs.com/veaxen/articles/9185250.html
相关资源：归并排序 C语言实现