归并排序

include "./common.php";
/*归并排序_递归法*/
$arr = [14,18,19,37,23,40,29,30,11,7,2,1,8,6,3,5,4] ;
$sorted_arr = mergeDivide($arr);
myPrint($sorted_arr);    // 1 2 3 4 5 6 7 8 11 14 18 19 23 29 30 37 40 [Finished in 0.1s]


// 拆分
function mergeDivide($arr){
    $count = count($arr);
    if($count<=1)return $arr;
    $len =  floor($count/2) ;
    $leftArr = array_slice($arr, 0, $len);
    $rightArr = array_slice($arr,$len );

    return mergeConquer(mergeDivide($leftArr),mergeDivide($rightArr));
}

// 合并
function mergeConquer($leftArr,$rightArr){
    $i=0;$j=0;
    $sorted_arr= [] ;

    while ($i<count($leftArr) && $j<count($rightArr)) {
        if($leftArr[$i]<=$rightArr[$j]){
            $sorted_arr[] = $leftArr[$i];
            $i++;
        }
        else{
            $sorted_arr[] = $rightArr[$j];
            $j++;
        }
    }

    if($i==count($leftArr)){
        $sorted_arr= array_merge($sorted_arr,array_slice($rightArr,$j));
    }else{
        $sorted_arr= array_merge($sorted_arr,array_slice($leftArr,$i));
    }

    return $sorted_arr;
}