<?php
// 递归
function mergeSort(&$arr, $left, $right) {
    if ($left < $right) {
        // 找出中间索引
        $mid = floor(($left + $right) / 2);
        // 对左边数组进行递归
        mergeSort($arr, $left, $mid);
        // 对右边数组进行递归
        mergeSort($arr, $mid + 1, $right);
        // 合并
        merge($arr, $left, $mid, $right);
    }
}
 
// 将两个有序数组合并成一个有序数组
function merge(&$arr, $left, $mid, $right) {
    $i = $left;     // 左数组的下标
    $j = $mid + 1;  // 右数组的下标
    $temp = array();// 临时合并数组
    // 扫描第一段和第二段序列，直到有一个扫描结束
    while ($i <= $mid && $j <= $right) {
        // 判断第一段和第二段取出的数哪个更小，将其存入合并序列，并继续向下扫描
        if ($arr[$i] < $arr[$j]) {
            $temp[] = $arr[$i];
            $i++;
        } else {
            $temp[] = $arr[$j];
            $j++;
        }
    }
    // 比完之后，假如左数组仍有剩余，则直接全部复制到 temp 数组
    while ($i <= $mid) {
        $temp[] = $arr[$i];
        $i++;
    }
    // 比完之后，假如右数组仍有剩余，则直接全部复制到 temp 数组
    while ($j <= $right) {
        $temp[] = $arr[$j];
        $j++;
    }
    // 将合并序列复制到原始序列中
    for($k = 0; $k < count($temp); $k++) {
        $arr[$left + $k] = $temp[$k];
    }
}
 
// 测试
$arr = [85, 24, 63, 45, 17, 31, 96];
mergeSort($arr, 0, count($arr) - 1);
print_r($arr);

<?php
//非递归
function mSort(&$arr) {
    $len = count($arr);
    $size = 1;
    while ($size <= $len - 1) {
        // 从第一个元素开始扫描，left 代表第一个分割的序列的第一个元素
        $left = 0;
        while ($left + $size <= $len - 1) {
            // mid 代表第一个分割的序列的最后一个元素
            $mid = $left + $size - 1;
            //right 代表第二个分割的序列的最后一个元素
            $right = $mid + $size;
            if ($right > $len - 1) { // 如果第二个序列个数不足size个
                //调整 right 为最后一个元素的下标即可
                $right = $len - 1;
            }
            // 调用归并函数，进行分割的序列的分段排序
            merge($arr, $left, $mid, $right);
            $left = $right + 1;
        }
        $size *= 2; // 范围扩大一倍
    }
}
 
// 将两个有序数组合并成一个有序数组
function merge(&$arr, $left, $mid, $right) {
    $i = $left;     // 左数组的下标
    $j = $mid + 1;  // 右数组的下标
    $temp = array();// 临时合并数组
    // 扫描第一段和第二段序列，直到有一个扫描结束
    while ($i <= $mid && $j <= $right) {
        // 判断第一段和第二段取出的数哪个更小，将其存入合并序列，并继续向下扫描
        if ($arr[$i] < $arr[$j]) {
            $temp[] = $arr[$i];
            $i++;
        } else {
            $temp[] = $arr[$j];
            $j++;
        }
    }
    // 比完之后，假如左数组仍有剩余，则直接全部复制到 temp 数组
    while ($i <= $mid) {
        $temp[] = $arr[$i];
        $i++;
    }
    // 比完之后，假如右数组仍有剩余，则直接全部复制到 temp 数组
    while ($j <= $right) {
        $temp[] = $arr[$j];
        $j++;
    }
    // 将合并序列复制到原始序列中
    /*for($k = 0; $k < count($temp); $k++) {
        $arr[$left + $k] = $temp[$k];
    }*/
    for ($i = $left, $k = 0; $i <= $right; $i++, $k++) {
        $arr[$i] = $temp[$k];
    }
}
 
// 测试
$arr = [85, 24, 63, 45, 17, 31, 96, 1];
mSort($arr);
print_r($arr);