8.5 归并排序

“归并”一词的中文含义就是合并、并入的意思，归并排序（Merge）是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

归并排序算法稳定，数组需要O(n)的额外空间，链表需要O(log(n))的额外空间，时间复杂度为O(nlog(n))，算法不是自适应的，不需要对数据的随机读取。

归并排序的步骤是：

1、对于分成两部分的数组，先左侧部分排好序，再右侧部分排好序，然后准备一个辅助数组；

2、用外排的方式，哪边小就将谁填进辅助数组；

3、当其中的一个数组转移完毕后，即指针指向的最后一个元素也进入辅助数组了，将另一个数组的剩余元素全部移入辅助数组。

例如：对于数组（5,2,0,1,4,3），我们将其分成两部分（5,2,0）和（1,4,3），两个数组分别进行排序为（0,2,5）和（1,3,4），index1指向数组1中的元素“0”，index2指向数组2中的元素“1”，此时index1指向的数组比较小，故“0”元素进入辅助数组，index1向后移动一位指向数组1中的元素“2”，再将index1和index2指向的元素进行比较，较小的进入辅助数组，当其中的一个数组转移结束后（在这里是数组2），将另一个数组（这里是数组1）剩下的元素全部移进辅助数组。

对于它的时间复杂度：

由于归并排序是递归过程，因此可以使用master公式计算复杂度

master公式：
 T(N) = a*T(N/b) + O(N^d)
  1) log(b,a) > d -> 复杂度为O(N^log(b,a))
  2) log(b,a) = d -> 复杂度为O(N^d * logN)
  3) log(b,a) < d -> 复杂度为O(N^d)

在这里，将数组均分成2份，左侧部分排好序，右侧部分排好序，数据量减半，故b = 2，发生了两回，故a = 2，两侧都排好序之后，进行外排，两个下标都要动，一共滑过了n

个数，然后将这些数放进辅助数组，故这里的d = 1 。所以，最后归并排序的复杂度是 2 * log（N/2）+ O（N）。

用php实现该算法：

<?php
header("content-type:text/html;charset=utf-8");
/*
 * 归并法排序：
 * master公式的使用
 * T(N) = a*T(N/b) + O(N^d)
 *  1) log(b,a) > d -> 复杂度为O(N^log(b,a))
 *  2) log(b,a) = d -> 复杂度为O(N^d * logN)
 *  3) log(b,a) < d -> 复杂度为O(N^d)
 *
 * 时间复杂度：O(N * logN);额外空间复杂度（help辅助数组）O（N）
 * */

function mergeSort(&$arr){
    if ($arr == null || count($arr) < 2) {
        return;
    }
    sortProcess($arr,0,count($arr) - 1);  //对0到终点的数据进行排序
}

//函数功能：执行排序递归过程
function sortProcess(&$arr,$l,$r){
    if ($l == $r) {                    //这个范围只有一个数，表明已经排好了
        return true;
    }

    $mid = floor(($l + $r)/2);         //求中点的位置

    sortProcess($arr,$l,$mid);        //左部分进行排序, T(N/2)
    sortProcess($arr,$mid+1,$r);      //右部分进行排序, T(N/2)
    merge($arr,$l,$mid,$r);               //整体归并排序，传参的意义：从l到min已经排好序，mid+1到r已经排好序, O(N)
    //T(N) = 2T(N/2) + O(N)
    //根据master公式O(N^d * logN)，复杂度为O(N * logN)
}

//函数功能：从l到min已经排好序，mid+1到r已经排好序，如何让它整体有序
function merge(&$arr,$l,$mid,$r){
    $help = array();                  //初始化辅助数组
    $i = 0;                            //合并数组的索引
    $p1 = $l;                          //p1指向左边数组的起始位置，相当于index1
    $p2 = $mid + 1;                    //p2指向右边数组的起始位置，相当于index2
    while($p1<=$mid && $p2<=$r){      //这是谁小填谁的过程
        $help[$i++] = $arr[$p1] < $arr[$p2] ? $arr[$p1++] : $arr[$p2++]; //谁小填谁的过程中还伴随着指针的右移
    }
    //两个必有且只有一个越界，即使这两个while是顺序执行的，但是只会执行一个
    while($p1<=$mid){                //p2越界，p1数组还有值，那就要把p1剩下的拷贝进辅助数组，此时不会执行下一个while循环
        $help[$i++] = $arr[$p1++];
    }

    while($p2<=$r){                //进入这个while的时候，前一个while肯定没有执行，p1越界，p2数组还有值，那就要把p2剩下的拷贝进辅助数组
        $help[$i++] = $arr[$p2++];
    }

    for($i = 0;$i<count($help);$i++){ //把辅助数组的数据全部填进原数组
        $arr[$l+$i] = $help[$i];
    }
}

$arr = [2,33,45,22,64,67,12,1,0,9];
mergeSort($arr);
print_r($arr);