1、归并排序的实现
归并排序也利用了分治法的思想，首先将序列分成左右两部分，将左右两部分分别排序，然后将有序的两个子序列进行合并（即merge操作），程序是递归进行的，主函数实现如下：
//归并排序主函数void merge_sort(int* a,int first,int last){int mid;if(first<last){mid = (first+last)/2;merge_sort(a,first,mid);merge_sort(a,mid+1,last);//merge(a,first,mid,last);//merge操作方法1，普通的merge操作improved_merge(a,first,mid,last);//meger操作方法2，优化的merge操作}}待排序的子序列从first开始，以last结尾，递归调用merge_sort，当first==last的时候停止，然后将已经有序的子序列进行合并操作。
2、普通的merge操作普通的merge操作在合并长度为k和m的子序列时，需要消耗k+m个空间来创建一个临时数组，空间复杂度为O(n)，实现如下：
//将从first到mid的子串和从mid+1到last的子串合并void merge(int* a,int first,int mid,int last){ int* c;int i = first,j = mid+1;int k = 0;//合并n个元素需要n个空间，空间复杂度为O(n)c = (int*)malloc(sizeof(int)*(last-first+1));while(i<=mid && j<=last){if(a[i]<=a[j]){c[k++] = a[i++];}else{c[k++] = a[j++];} }while(i<=mid){c[k++] = a[i++];}while(j<=last){c[k++] = a[j++];}for(i=first,k=0;i<=last;i++,k++){a[i] = c[k];}}3、优化的merge操作
在合并长度为k和m的子串时，只需要min{k,m}的额外空间即可，首先申请大小为min{k,m}的空间，然后从子序列a和b中选择最右边的元素（即从子序列最大元素开始选），选择两个子序列中的较大者放在额外空间的右边，从右向左填充，额外空间填满之后再填充长度为max{k,m}的子序列，从最后一个开始填充，这种方法省了至少一半的空间，虽然空间复杂度仍未O(n)，实现如下：
//申请额外n/2个空间，如果两个子串大小不一样，则申请的空间//大小只需要为小的那个。选取两个子串中的较大的从右往左排序。//先填充额外空间c，，再填充已有的空间。void improved_merge(int* a,int first,int mid,int last){int* c;int i,j,k;//合并n个元素需要需要n/2个空间,虽然空间复杂度仍为O(n)c = (int*)malloc(sizeof(int)*(last-mid));i=mid,j=last; for(k=last-mid-1;k>=0;k–){//从右往左填充cif(a[i]>=a[j]){c[k] = a[i–];}else{c[k] = a[j–];}}k = mid;while(i>=first&&j>=mid+1){//填充aif(a[i]>=a[j]){a[k–] = a[i–];}else{a[k–] = a[j–];}}while(i>=first){a[k–] = a[i–];}while(j>=mid+1){a[k–] = a[j–];}for(i=mid+1,k=0;i<=last;i++,k++){//将c复制到a中a[i] = c[k];}}4、归并排序的时间复杂度分析
进行一次merge操作，worst case需要进行k+m-1次比较，即若k+m=n，需要进行n-1次比较。
递归表达式可以近似表示为：
T(n)=T(n/2)+T(n/2)+Cn。
由master theorem可得为nlgn，空间复杂度由上面分析可得为O(n)。
穿过紫堇，穿过木棉，穿过时影时现的悲喜和无常。
