大家好，我是向同学，我们今天来谈谈归并排序算法。
归并排序（MergeSort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（DivideandConquer）的一个非常典型的应用。
一、算法思想
归并排序的主要思想是分治法。主要过程是：
1.将n个元素从中间切开，分成两部分。
2.将剩下的数组通过递归的方式一直分割，直到数组的大小为1，此时只有一个元素，那么该数组就是有序的了。
3.从最底层开始逐步合并两个排好序的数列。把两个数组大小为1的合并成一个大小为2的有序数列，再把两个大小为2有序数列的合并成4的有序数列…直到全部小的数组合并起来。
二、思考
那么如何将两个有序数列合成一个有序的数列呢？
我们举个栗子把，一看就懂啦。
三、举个栗子
例如有数组arr[3,7,8,10,2,4,6,9];我们可以把这个数组分成两个有序的子序列。
分别为[3,7,8,10]和[2,4,6,9]，并将其合并为有序序列[2,3,4,6,7,8,9,10]。
第一步：
把这两个小的数组拆分为left数组和right数组。如下图所示，使用i指向left的第一个元素，使用j指向right的第一个元素。
第二步：
建立一个空数组arr,使用k指向数组第一个元素。
第三步：
比较i和j所指数字，将小的数字放在k所指位置。同时将小的数字所指位置和k所指位置向右移一位。
23,将2填入arr数组，同时右移j和k。
34,将3填入arr数组，同时右移i和k。
47，将4填入arr数组，同时右移j和k。
67，将6填入arr数组，同时右移j和k。
79，将7填入arr数组，同时右移i和k。
89，将8填入arr数组，同时右移i和k。
，将9填入arr数组，同时右移j和k。
可以发现此时right数组已经填完了，所以此时只需要把left数组剩下的数字填入arr即可。
一顿操作猛如虎，这样就把两个有序的数组通过归并的方式排好顺序啦，是不是很赞。
那么问题来了，难道归并排序只能排这种有序的数组么？
那出现一个无序的数组该咋办呢？例如这个数组现在变为arr[8,7,2,10,3,9,4,6];
四、问题解决
此刻需要运用分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
其实上面第三部分就是治(conquer)的过程，将两个有序的序列合成为一个有序的序列。
小栗子：图解无序序列进行希尔排序。
五、算法实现
#includestdio.hvoidmerge(intarr[],intL,intM,intR){intLEFT_SIZE=M-L;intRIGHT_SIZE=R-M+1;intleft[LEFT_SIZE];intright[RIGHT_SIZE];inti,j,k;//填充左边的数组for(i=L;iM;i++){left[i-L]=arr;}//填充右边的数组for(i=M;i=R;i++){right[i-M]=arr;}//for(inti=0;iLEFT_SIZE;i++){//printf("%d\n",left);//}////for(inti=0;iRIGHT_SIZE;i++){//printf("%d\n",right);//}//合并数组i=0;j=0;k=L;while(iLEFT_SIZEjRIGHT_SIZE){if(leftright[j]){arr[k]=left;i++;k++;}else{arr[k]=right[j];j++;k++;}}while(iLEFT_SIZE){arr[k]=left;i++;k++;}while(jRIGHT_SIZE){arr[k]=right[j];j++;k++;}}voidmergeSort(intarr[],intL,intR){if(L==R){return;}else{intM=(L+R)/2;mergeSort(arr,L,M);mergeSort(arr,M+1,R);merge(arr,L,M+1,R);}}intmain(){//intarr[]={3,7,8,10,2,4,6,9};intarr[]={8,7,2,10,3,9,4,6};intL=0;intM=4;intR=7;mergeSort(arr,L,R);for(inti=0;i=R;i++){printf("%d\n",arr);}}
输出：
六、算法分析
时间复杂度：O(nlogn)。
空间复杂度：O(N)，归并排序需要一个与原数组相同长度的数组做辅助来排序。
稳定性：稳定，因为交换元素时，可以在相等的情况下做出不移动的限制，所以归并排序是可以稳定的。
七、适用场景
归并排序需要一个跟待排序数组同等空间的临时数组，因此，使用归并排序时需要考虑是否有空间上的限制。如果没有空间上的限制，归并排序是一个不错的选择。