在之前我写过关于归并排序的介绍，《排序算法学习之路——归并排序》。据现在已经有很长时间了。现在再重新进行规整，对归并排序再从代码层面详细说一下。
归并排序算法按照惯例，对于排序算法。我们还是先罗列概念
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
合并通过概念我们也能看出，既然是归并排序，那核心的问题就是如何进行归并了。这可以归结为从小往大的一个合并问题。
给定我们一组数据
我们通过分治策略，将其拆分。直到不能拆为止，想要达到的效果如下
这就是我们最终用来进行归并的拆分后的数组。下面开始合并
我们可以看到，每两个数组进行合并。合并之后的新数组是有序的。然后新数组之间再两两合并，直到合并为一个最终的数组。
下面我们以最后一步合并为例子，介绍一下两个数组之间合并的细节步骤。
第一步、 sl 和 sr位置上的元素进行比较，值小的一方的元素放入新数组，然后对应的索引 sl/sr 向前进一位。这里 sl位置上的2小，因此将2 放入新数组，sl移到该组的下一个元素
第二步、再次将 sl 和 sr 位置上的元素进行比较，3 比 6 小，因此 3放入新数组，sl再次移动到下一个元素
第三步、二者继续比较，此时 sr上的 6 要比 sl上的7小。因此将6放入新的数组，sr移动到该组的下一个元素
第四步、重复上面的比较过程，直到有一组先于另一组全部放入到新数组中
最后，此时的 sl一组已经全部排序完成了，而对于 sr一组剩余的元素可以直接放入新数组。因为每一组之内的元素都是有序的。
此时我们看到整个归并过程已经完成了。下面我们看一下合并过程的代码（以下代码用 PHP 编写）
function Merge($arr,$l,$m,$r) { $t = $arr; $lstart = $l; $rstart = $m+1; while($l < $r) { if($lstart > $m || $rstart > $r) break; if($arr[$lstart] > $arr[$rstart]) { $t[$l++] = $arr[$rstart++]; }else{ $t[$l++] = $arr[$lstart++]; } } $start = $l; $end = $r; if($lstart <= $m) { $start = $lstart; $end = $m; }elseif($rstart <= $r) { $start = $rstart; $end = $r; } while($start <= $end) { $t[$l++] = $arr[$start++]; } $arr = $t; return $arr; }