归并排序是一种”高级”的排序方法，其是”分治思想”一个典型的应用，这种排序方式效率很高，时间复杂度是O(NlogN)，并且该排序算法还是稳定的。接下来，我们说一下，归并排序的基本的思路：
假如我们当前有一个随机的数组,需要对它进行排序操作。
首先，我们先对数组进行拆分操作，要将数组拆分成n(数组的长度)个长度的长度为1的数组。
(1):当前数组的长度为10，那我们就取出索引为mid(mid = 数组的长度length/2)的元素作为切分点。将数组中的[0,mid-1]部分的元素以及[mid,length-1]部分的元素分别截取出来，作为left数组以及right数组
(2):经过上面的切分以后，原数组一分为二。然后检测当前获取的left数组以及right数组的长度是否为1，如果数组长度仍然是大于1，就继续进行切分操作，直到切分出来的每一个left数组以及right数组的长度都为1。
(3):切分出长度为1的left数组以及right数组以后，就可以将数组进行合并操作。假设当前的left数组为[6],right数组为[2],那么这两个数组一定是由数组[6,2]切分而来的。合并数组的时候有一个非常重要的前提，那就是每一个即将合并left数组或者right数组都是有序的(这一点很好理解，当left/right数组的长度为1的时候，数组中的元素本身就是有序的。两个长度为1的数组进行合并后会生成一个新的有序的数组，这个新的有序的数组还会参与到下面的合并中去，依次类推，每一个即将合并的left/right数组都是有序的)。依次类推，不断的继续两个有序数组的合并操作，直到合并完成。
可以看一下，下面的图解：
下面是用PHP写了一下归并排序，一开始看了网上的一些帖子，借助PHP中一些内置函数来实现，具体的代码如下:
上面的代码很简单，相信大家都能看的明白。如果同学看过其他语言的关于归并的实现，就会发现用PHP实现，和其他语言还是有一些比较大的差异的，主要是上面的实现方式是利用了PHP的内置函数在数组拆分阶段将数组一分为二，创建出两个新的数组，而其他的语言基本都是用两个变量指向当前的数组最前的位置以及最后的位置来模拟出两个”新”的数组。下面，我贴出用模拟生成”新”数组的方式来实现的代码：
//随机数组$rand_arr = [9,8,7,6,5,4,3,2,1,0];//第一步，分割数组// $l以及$r都是用来记录数组中元素所对应的索引// 默认$l指向数组的头部，即$l=0 $r指向数组的尾部，即$r=数组的长度-1function divide_arr(&$arr,$l,$r){ //同上，计算出进行"分割"的中间点 $mid = floor(($l+$r)/2); //区别在于这里，我们并不是直接截取出数组中的部分元素，放到新的数组中 //而是修改了传递到divide_arr中的参数$l以及$r的值 divide_arr($arr,$l,$mid); divide_arr($arr,$mid+1,$r); merge_arr($arr,$l,$mid,$r);}//第二步，进行合并function merge_arr($arr,$l,$mid,$r){ $i=$l; $j=$mid+1; //创建一个新的数组，用来存放比较完成的部分(有序) $new_arr=[]; echo "左数组"; print_r(array_slice($arr,$l,$mid-$l+1)); echo "右数组"; print_r(array_slice($arr,$mid+1,$r-$mid)); while($i<=$mid && $j<=$r){ //进行数据的交换 if($arr[$i]<=$arr[$j]){ $new_arr[]=$arr[$i]; $i++; }else{ $new_arr[]=$arr[$j]; $j++; } } while($i<=$mid){ $new_arr[] = $arr[$i]; $i++; } while($j<=$r){ $new_arr[]=$arr[$j]; $j++; } //将排好序的数组与$arr相对应进行修改 for($k=0,$i=$l;$i<=$r;$k++,$i++){ $arr[$i] = $new_arr[$k]; } print_r($new_arr); print_r($arr); echo "
"; echo "";}复制代码 上面的实现方式与上面提到的第一种实现方式相对比，通过不断修改数组拆分过程中调用divide_arr()函数中的$l以及$r变量的值，来”动态划分”当前需要处理的数组部分，而不是采用PHP中的内置函数来截取需要处理数组部分，在一定程度上提高了性能。为了方便大家的理解，我打印出程序执行的部分步骤，给大家看一下:
(1)左数组
Array ( [0] => 9 )右数组Array ( [0] => 8 )new_arrArray ( [0] => 8 [1] => 9 )arrArray ( [0] => 8 [1] => 9 [2] => 7 [3] => 6 [4] => 5 [5] => 4 [6] => 3 [7] => 2 [8] => 1 [9] => 0 )(2)左数组Array ( [0] => 8 [1] => 9 )右数组Array ( [0] => 7 )new_arrArray ( [0] => 7 [1] => 8 [2] => 9 )arrArray ( [0] => 7 [1] => 8 [2] => 9 [3] => 6 [4] => 5 [5] => 4 [6] => 3 [7] => 2 [8] => 1 [9] => 0 )(3)左数组
Array ( [0] => 6 )右数组Array ( [0] => 5 )new_arrArray ( [0] => 5 [1] => 6 )arrArray ( [0] => 7 [1] => 8 [2] => 9 [3] => 5 [4] => 6 [5] => 4 [6] => 3 [7] => 2 [8] => 1 [9] => 0 )(4)左数组
Array ( [0] => 7 [1] => 8 [2] => 9 )右数组Array ( [0] => 5 [1] => 6 )new_arrArray ( [0] => 5 [1] => 6 [2] => 7 [3] => 8 [4] => 9 )arrArray ( [0] => 5 [1] => 6 [2] => 7 [3] => 8 [4] => 9 [5] => 4 [6] => 3 [7] => 2 [8] => 1 [9] => 0 )………
说到这个，不知道大家发现没有，上面的两种实现方式，都是至上而下的实现方式(就是先将数组中的元素进行拆分，然后再进行合并)，其实我们也可以至下而上的方式来实现归并排序(就是不递归的进行数组的拆分，而是首先直接进行数组中的元素划分为n组(每组的元素个数为2)，然后对每组中的元素进行排序操作，当n组排序完成后，我们就相当于创建了n组有序的数组。然后我们在对数组中的元素划分为m组(每组的元素个数为4)，再进行排序操作，依次类推…)，看下面的代码的实现:
复制代码
不管是至上而下还是至下而上的实现方式，都是利用了分治的思想，先对部分元素进行排序操作，然后不断的进行合并(由于合并过程中永远是两个有序的数组进行比较，所有速度比较快)，这种思想非常常用。