Java中常用的6种排序算法详细分解(4)

归并排序采用的是递归来实现，属于“分而治之”，将目标数组从中间一分为二，之后分别对这两个数组进行排序，排序完毕之后再将排好序的两个数组“归并”到一起，归并排序最重要的也就是这个“归并”的过程，归并的过程中需要额外的跟需要归并的两个数组长度一致的空间，比如需要规定的数组分别为： [3, 6, 8, 11] 和 [1, 3, 12, 15] （虽然逻辑上被划为为两个数组，但实际上这些元素还是位于原来数组中的，只是通过一些 index 将其划分成两个数组，原数组为 [3, 6, 8, 11, 1, 3, 12, 15 ，我们设置三个指针 lo, mid, high 分别为 0,3,7 就可以实现逻辑上的子数组划分）那么需要的额外数组的长度为 4 + 4 = 8 。归并的过程可以简要地概括为如下：

1） 将两个子数组中的元素复制到新数组 copiedArray 中，以前面提到的例子为例，则 copiedArray = [3, 6, 8, 11, 1, 3, 12, 15] ；

2） 设置两个指针分别指向原子数组中对应的第一个元素，假定这两个指针取名为 leftIdx 和 rightIdx ，则 leftIdx = 0 （对应 copiedArray 中的第一个元素 [3] ）， rightIdx = 4 （对应 copiedArray 中的第五个元素 [1] ）；

3） 比较 leftIdx 和 rightIdx 指向的数组元素值，选取其中较小的一个并将其值赋给原数组中对应的位置 i ，赋值完毕后分别对参与赋值的这两个索引做自增 1 操作，如果 leftIdx 或 rigthIdx 值已经达到对应数组的末尾，则余下只需要将剩下数组的元素按顺序 copy 到余下的位置即可。

下面给个归并的具体实例：

第一趟： 
 
辅助数组 [21 , 28, 39 | 35, 38] （数组被拆分为左右两个子数组，以 | 分隔开） 
 
[21 ,  ,  ,  ,  ] （第一次 21 与 35 比较 , 左边子数组胜出， leftIdx = 0 ， i = 0 ） 
 
第二趟： 
 
辅助数组 [21, 28 , 39 | 35, 38] 
 
[21 , 28,  ,  ,  ] （第二次 28 与 35 比较，左边子数组胜出， leftIdx = 1 ， i = 1 ） 
 
第三趟： [21, 28, 39 | 35 , 38] 
 
[21 , 28 , 35,  ,  ] （第三次 39 与 35 比较，右边子数组胜出， rightIdx = 0 ， i = 2 ） 
 
第四趟： [21, 28, 39 | 35, 38 ] 
 
[21 , 28 , 35 , 38,  ] （第四次 39 与 38 比较，右边子数组胜出， rightIdx = 1 ， i = 3 ） 
 
第五趟： [21, 28, 39 | 35, 38] 
 
[21 , 28 , 35 , 38 , 39] （第五次时右边子数组已复制完，无需比较 leftIdx = 2 ， i = 4 ）
以上便是一次归并的过程，我们可以将整个需要排序的数组做有限次拆分（每次一分为二）直到分为长度为 1 的小数组为止，长度为 1 时数组已经不用排序了。在这之后再逆序（由于采用递归）依次对这些数组进行归并操作，直到最后一次归并长度为 n / 2 的子数组，归并完成之后数组排序也完成。