全面了解归并排序算法及代码实现

在之前我写过关于归并排序的介绍，《排序算法学习之路——归并排序》。据现在已经有很长时间了。现在再重新进行规整，对归并排序再从代码层面详细说一下。

归并排序算法

按照惯例，对于排序算法。我们还是先罗列概念

---

合并

通过概念我们也能看出，既然是归并排序，那核心的问题就是如何进行归并了。这可以归结为从小往大的一个合并问题。

给定我们一组数据

我们通过分治策略，将其拆分。直到不能拆为止，想要达到的效果如下

这就是我们最终用来进行归并的拆分后的数组。下面开始合并

我们可以看到，每两个数组进行合并。合并之后的新数组是有序的。然后新数组之间再两两合并，直到合并为一个最终的数组。

下面我们以最后一步合并为例子，介绍一下两个数组之间合并的细节步骤。

第一步、 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;
}