05-归并排序

/**
 * 归并排序: 对半拆分元素, 拆到底后, 比较左右两边元素, 让其有序后, 回归
 * 时间复杂度: O(nlogn)
 * 空间复杂度: O(n)
 * 稳定排序(相等元素的顺序不会改变)
 */

function mergeSort(&$arr, $start, $end) {
    if ($start < $end) {
        $mid = floor(($start + $end) / 2);
        mergeSort($arr, $start, $mid);
        mergeSort($arr, $mid + 1, $end);
        merge($arr, $start, $mid, $end);
    }
}

function merge(&$arr, $start, $mid, $end) {
    $i = $start;
    $j = $mid + 1;
    $temp = [];
    while( $i <= $mid && $j <= $end) {
        if($arr[$i] < $arr[$j]) {
            $temp[] = $arr[$i];
            ++$i;
        } else {
            $temp[] = $arr[$j];
            ++$j;
        }
    }

    while($i <= $mid) {
        $temp[] = $arr[$i];
        ++$i;
    }

    while($j <= $end) {
        $temp[] = $arr[$j];
        ++$j;
    }

    for ($k = 0; $k < count($temp); ++$k) {
        $arr[$k + $start] = $temp[$k];
    }
}

$arr = [38, 19, 29, 91, 85, 12, 41, 21];
mergeSort($arr, 0, count($arr) - 1);
print_r($arr);