谈谈归并排序

归并排序是建立在归并操作上的一种排序算法,该算法是采用分治法的典型的应用。

若数组的元素个数为N，其排序思想为：

①、分为log2N个小组，若最终结果为浮点数，即向上取整。分组之后，每一个小组只有一个元素，默认为有序的小组。

②、将每一个小组进行两两归并，并且在归并时进行从小到大的排序。如上图所示，8个小组归并同时从小到大排序，成为4个有序的小组；4个小组归并同时从小到大排序，成为2个有序的小组；2个小组归并同时从小到大排序，成为1个有序的小组。此时，这个小组就是数组本身自己，故，这个数组的排序工作此时已经完成。

说完了总体的归并思想，说一下小组之间的归并的做法，以2个小组归并成一个小组为例。

首先应该复制一份数组的元素，要知道，虽然归并排序的时间复杂度为O(n*logn)，但是其空间复杂度为O(n)，也就是说数组有多大的空间，排序就需要多大的辅助空间，在内存和硬盘相对便宜的今天，执行效率的提高似乎才是我们程序员最应该关心的问题。

除此之外，我们还需要几个标志位来辅助归并操作。k表示原数组中将要被存放归并2个小数组后的元素的下标；l(left)表示第一个归并小组的最左的下标的位置，相对应的r(right)表示第二个归并小组的最右的下标的位置，可以这么理解，我们进行归并的数组的下标范围为[l,r]，而m则是两个小组的中间位置，也是分隔点。

初始化i和j都等于0，此时比较arr[i]和arr[j],若arr[i]>arr[j]，则arr[k]=arr[j]，与此同时，k++,j++，而i却不变；否则，则arr[k]=arr[i]，与此同时，k++,i++，而j却不变。

循环往复，直到i==middle,或者j==r,此时说明有一个小组的归并操作已经完成了，将另外一个小组的元素顺次存放到arr[k]中即可完成归并操作。

看看代码。

上图为归并排序可以被外界调用的函数，第一个参数为要进行归并排序的数组，第二个参数为数组的大小。而在其内部是调用了一个名为__mergeSort()的函数，那个是内部调用的函数，相信有Python编程经验的程序员也看出来了，这个函数借鉴了Python的命名方案，即在用Python编写的类中，私有方法都是要以__开头的，这取代了在C++和Java中对私有方法进行private声明的做法。

这个函数的第1个参数是要进行归并排序的数组，第2个参数是数组的排序的左起点，第3个参数是数组的排序的右终点，即这个函数是对arr[L……r]进行归并排序的。

而在其内部，当r-L

接着说内部代码，先得获取mid，即归并的两部分的中间位置，即以这个中间位置将数组分成2个部分，对着2个部分进行归并排序。这个使用递归的思想，向对左部分进行归并，将左部分分成2个部分进行归并排序，直到左部分已经排序完成；再对右部分进行归并排序，将右部分分成2个部分进行归并排序，直到右部分已经排序完成；最后将左右部分合成一个整体。但是，上图代码做了一个优化，即只有当左部分的元素大于右部分的元素，即此时顺序仍然不正确时才进行左右两部分的排序；若左部分小于右部分，而此时左右部分皆在上面几行代码排序完成，就可以认为整个数组已经是有序的了，此时就没必要进行归并排序了。

总体的 归并排序思想讲解完毕，接下来说说左右两部分的归并过程。

我们要新开辟一片空间，这个空间是要和排序的数组片段等大的，这个辅助的数组时用来进行左右两部分的比较的，然后将合适的元素写入到原数组合适的位置中。这份代码完全是将上述的合并过程做了一个实现，并且在代码中已有清晰的注释，此时不再赘述。