归并排序的递归实现

1. 归并排序(merge-sort)是建立在归并操作上的一种有效的排序算法，该算法采用分治法(divide and conquer)的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
2. 归并排序过程：比较a[i]和a[j]的大小，将第一个有序表中的a[i]复制到r[k]中，并令i和k分别加1；否则讲第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的元素，从此得到一个新的有序表。
3. 通常来讲，我们采用递归方式实现完整的归并排序，先把原始数组a中下标[start,end]用中点mid二分，接着把左边子区间A[start,mid]排序，再把右边子区间B[mid+1, end]排序，最后再用一次归并操作把A\B合并成最终有序表C[start,end]。

1. 代码如下：

<?php
/**
 * 递归归并排序[正序]
 * author: nsimple
 * date: 2016/12/14
 * link: http://nsimple.top
 */

//归并排序
function mergeSort(&$arr, $startKey, $midKey, $endKey) {
    //临时堆
    $tmp = array();
    $i   = $startKey;
    $j   = $midKey + 1;
    $k   = $startKey;
    for(; $i <= $midKey && $j<=$endKey; $k++) {
        //每次从两堆中取最小值放到临时堆
        if($arr[$i] <= $arr[$j]) {
            $min = $arr[$i++];
        } else {
            $min = $arr[$j++];
        }
        $tmp[$k] = $min;
    }

    //将余下部分存放到临时堆中
    while($i <= $midKey) {
        $tmp[$k++] = $arr[$i++];
    }
    while($j <= $endKey) {
        $tmp[$k++] = $arr[$j++];
    }
    //每次归并排序结果
    for ($i = $startKey; $i <= $endKey; $i++) {
        $arr[$i] = $tmp[$i];
    }
    process($arr);
}

//记录排序步骤
function process($arr = array())
{
    static $step = 0;
    echo '<pre>';
    $step++;
    echo '第' . $step . '步排序:';
    print_r($arr);
    echo '</pre>';
}
//递归归并排序
function recursionMergeSort(&$arr, $startKey = 0, $endKey = 0) {
    if($startKey < $endKey) {
        $midKey = floor(($startKey + $endKey)/2);
        //左子序列递归归并排序
        recursionMergeSort($arr, $startKey, $midKey);
        //右子序列递归归并排序
        recursionMergeSort($arr, $midKey + 1, $endKey);
        //左右子序列归并
        mergeSort($arr, $startKey, $midKey, $endKey);
    }
}

2. 测试排序：

//测试数据
$arr = array(
    '9'  => 4,
    '10' => 8,
    '11' => 7,
    '12' => 5,
    '13' => 1,
    '14' => 6,
    '15' => 3,
    '16' => 0
);
//开始执行排序
recursionMergeSort($arr, 9, 16);

3. 结果如下：

第1步排序:Array
(
    [9] => 4
    [10] => 8
    [11] => 7
    [12] => 5
    [13] => 1
    [14] => 6
    [15] => 3
    [16] => 0
)
第2步排序:Array
(
    [9] => 4
    [10] => 8
    [11] => 5
    [12] => 7
    [13] => 1
    [14] => 6
    [15] => 3
    [16] => 0
)
第3步排序:Array
(
    [9] => 4
    [10] => 5
    [11] => 7
    [12] => 8
    [13] => 1
    [14] => 6
    [15] => 3
    [16] => 0
)
第4步排序:Array
(
    [9] => 4
    [10] => 5
    [11] => 7
    [12] => 8
    [13] => 1
    [14] => 6
    [15] => 3
    [16] => 0
)
第5步排序:Array
(
    [9] => 4
    [10] => 5
    [11] => 7
    [12] => 8
    [13] => 1
    [14] => 6
    [15] => 0
    [16] => 3
)
第6步排序:Array
(
    [9] => 4
    [10] => 5
    [11] => 7
    [12] => 8
    [13] => 0
    [14] => 1
    [15] => 3
    [16] => 6
)
第7步排序:Array
(
    [9] => 0
    [10] => 1
    [11] => 3
    [12] => 4
    [13] => 5
    [14] => 6
    [15] => 7
    [16] => 8
)

4. 原始数组的元素不一定要求是2的N次幂, 当前案例二分拆分的时候，会用舍去法取中位的key。
5. 倒序实现只需排序的时候把最大的值依次复制到临时堆中即可