归并排序

这里使用的语言是PHP，但是语言都是相通的，用别的语言也可以实现，可以参考这里自行实现别的语言版本

/**
 * 归并排序
 */
function mergeSort(&$arr)
{
    $arr_len = count($arr);
    if ($arr_len = $r) {
        return;    
    }
    $mid = intval(($l + $r) / 2);
    merge_sort($arr, $l, $mid);
    merge_sort($arr, $mid + 1, $r);
    mergeData($arr, $l, $mid,$r);    
}
function mergeData(&$arr, $l, $mid,$r){

        //将数组arr[l...mid]和arr[mid + 1...r]两部分进行合并
        /**
         * 写法1：
         */
        $temparr = [];
        $i = $l;
        $k = $l;
        $j = $mid + 1;
        while($i != $mid + 1 && $j != $r+1)
        {
            if($arr[$i] >= $arr[$j]){
                $temparr[$k++] = $arr[$j++];
            }
            else{
                $temparr[$k++] = $arr[$i++];
            }
        }

        //将第一个子序列的剩余部分添加到已经排好序的 $temparr 数组中
        while($i != $mid+1){
            $temparr[$k++] = $arr[$i++];
        }
        //将第二个子序列的剩余部分添加到已经排好序的 $temparr 数组中
        while($j != $r+1){
            $temparr[$k++] = $arr[$j++];
        }
        for($i=$l; $i $mid) {
        //         $arr[$k] = $aux[$j - $l];
        //         $j++;
        //     }elseif($j > $r) {
        //         $arr[$k] = $aux[$i - $l];
        //         $i++;
        //     }elseif($aux[$i - $l]