归并排序归并排序算法的核心是“归并”，即将两个有序数组组合成一个更大的有序数组。归并排序的原理上面说过，归并排序的核心是“归并”。如果对一个数组进行排序，把数组从中间分成两部分，分别对两部分进行排序，然后将排序好的合并在一起，那么整个数组就会变成一个更大的有序数组。比如下图，说明mergesort使用的思想是divideandconquer，即分而治之。将一个复杂的问题分解成两个或多个大小相同或相近的子问题，然后不断细化。当子问题足够简单可以解决时，那么复杂问题也可以解决。这和递归的思想很像。递归也是把大问题细化成小问题，找出终止条件和递归公式。分而治之算法通常使用递归实现。分治思想是一种解决问题的处理思想，而递归是一种编程技术，两者不会冲突。上面说了归并排序可以用递归来实现，所以现在先写递归公式和终止条件。#递归公式merge_sort(a...b)=merge(merge_sort(a...k),merge_sort(k+1,b))#终止条件a>=b，这里不继续分解解释上面该公式没有详细说明终止条件。这里，如果索引a大于等于索引b，则表示已经到达数组末尾，不能再继续细分了。再说说递归公式，merge_sort(a...b)，意思是对索引为a到k的数组进行排序。这里，拆分转化为两个子问题，merge_sort(a...k)和merge_sort(k+1...b)，其中k表示原数组的中间位置。merge()函数的意思是当两个排序后的子数组合并时，可以使原数组排序。现在将这个递归公式转化为代码（这里使用伪代码）：#nums代表数组，a是起点，b是数组末尾的索引defmerge_sort(nums,a,b):#终止条件ifa>=b:return#取中间位置k=(a+b)//2#递归分治merge_sort(nums,a,k)merge_sort(nums,k+1,b)merge(nums[a...b],nums[a...k],nums[k+1,b])merge()函数的作用是将后两个子数组合并为nums[a...b].现在主要的问题是分解后如何实现排序和合并？先用一个简单的例子，如下图：先申请一个临时数组temp，定义指针i和j分别指向两个子数组的首元素。比较nums[i]、nums[j]，将较小的元素放入临时数组，将元素的指针向右移动。循环上述过程，直到将其中一个子数组的数据全部放入临时数组。这个时候把其他数组的剩余部分放到临时数组中。这个临时数组就是最后合并的结果，直接复制回原来的数组即可。现在用伪代码实现这个过程：defmerge(nums[a...b],nums[a...k],nums[k+1,b]):#length表示数组的大小temp=[0]*length#初始化指针，i,j,tii,j,ti,=a,k+1,0#取一个小的值放入一个临时数组中，while(i<=kandj<=b):if(nums[i]<=nums[j]):temp[ti]=nums[i]i+=1else:temp[ti]=nums[j]j+=1ti+=1#合并时，会出现一个数组，全部放入临时数组中，#另一个数组还有剩余，这里也把剩下的放到临时数组中ifi
