function merge_sort(&$A, $p, $r){
        if($p < $r){
            $q = floor(($p + $r)/2);
            merge_sort($A, $p, $q);
            merge_sort($A, $q+1, $r);
            merge($A, $p, $q, $r);
        }
    }
    //第一种
    function merge(&$A, $p, $q, $r){    //哨兵牌法
        $n1 = $q - $p + 1;
        $n2 = $r - $q;
        for($i = 0; $i < $n1; $i++){
            $L[$i] = $A[$p+$i];
        }
        for($j = 0; $j < $n2; $j++){
            $R[$j] = $A[$q+$j+1];
        }
        //防止越界(哨兵)
        $L[$n1] = $R[$n2] = PHP_INT_MAX;
        $i = $j = 0;
        for($k = $p; $k <= $r; $k++){
            if($L[$i] <= $R[$j]){
                $A[$k] = $L[$i];
                $i++;
            }else{
                $A[$k] = $R[$j];
                $j++;
            }
        }
    }
    //第二种
    function merge(&$A, $p, $q, $r){    
        $n1 = $q - $p + 1;
        $n2 = $r - $q;
        for($i = 0; $i < $n1; $i++){
            $L[$i] = $A[$p+$i];
        }
        for($j = 0; $j < $n2; $j++){
            $R[$j] = $A[$q+$j+1];
        }    
        $i = $j = 0;
        $k = $p;
        while($i<$n1 && $j<$n2){
            if($L[$i] <= $R[$j]){
                $A[$k++] = $L[$i++];
            }else{
                $A[$k++] = $R[$j++];
            }
        }
        
        for(; $i<$n1; $i++){
            $A[$k++] = $L[$i];
        }
        for(; $j<$n2; $j++){
            $A[$k++] = $R[$j];
        }
    }

特别申明：本站的主旨在于收集互联网运营相关的干货知识，给运营小伙伴提供便利。 网站所收集到的公开内容均来自于互联网或用户投稿，并不代表本站认同其观点， 也不对网站内容的真实性负责，如有侵权，请联系站长删除