php归并实现排序

归并排序原理

归并排序采用分治法，将数组递归拆分为最小单元（单个元素），再两两合并为有序序列。其时间复杂度为O(n log n)，是稳定排序算法。

PHP实现步骤

拆分阶段 通过递归将数组不断二分，直到子数组长度为1：

function mergeSort(array $array): array {
    if (count($array) <= 1) {
        return $array;
    }
    $mid = (int)(count($array) / 2);
    $left = array_slice($array, 0, $mid);
    $right = array_slice($array, $mid);
    return merge(mergeSort($left), mergeSort($right));
}

合并阶段 合并两个有序数组时，比较头部元素并插入结果数组：

function merge(array $left, array $right): array {
    $result = [];
    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] <= $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }
    }
    return [...$result, ...$left, ...$right];
}

使用示例

$unsorted = [5, 2, 9, 1, 5, 6];
$sorted = mergeSort($unsorted);
print_r($sorted); // 输出 [1, 2, 5, 5, 6, 9]

优化方向

对于大规模数据，可改用迭代方式避免递归栈溢出。小规模子数组时切换为插入排序能提升实际性能。