Объяснение сортировки слиянием с PHP

Question

Функция слияния работает правильно. У меня 2 запроса в сортировке слиянием 1) Я не могу понять, почему функция «слияние» вызывает здесь в третий раз (print execute) здесь, когда условие count == 1 встречается два раза как для левого, так и для правого все вместе. 2) Если я прокомментирую возвращение $ x, то при печати $ x в третий раз будет показан пустой массив, в противном случае $ x покажет отсортированный массив в третий раз, почему?

$arr= array(4,2,7,5);
$count= count($arr);
//Merge Sort

$result= merging($arr);
//echo "<pre>"; print_r($result); exit;
function merging($arr)
{
    $count= count($arr);
    if($count==1){ return $arr; }   

    $mid= ceil($count/2);
    $left= array_slice($arr,0,$mid);
    $right= array_slice($arr,$mid);

    $left= merging($left);
    $right= merging($right);
    echo "execute";
    $x=  merge($left,$right);
    echo "<pre>"; print_r($x); //exit;
    //return $x;
} 


function merge($left,$right)
{  
    //echo "<pre>"; print_r($left);
    //echo "<pre>"; print_r($right);
    $l=0; $r=0; $temp=[];
    while($l<count($left) && $r<count($right))
    {
        if($left[$l]> $right[$r])
        {
            $temp[]= $right[$r];
            $r++; 
        }else{
            $temp[]= $left[$l];
            $l++;
        }
    }
    while($l < count($left))
    {
        $temp[]= $left[$l];
            $l++;
    }

    while($r < count($right))
    {
        $temp[]= $right[$r];
            $r++;
    }
    return $temp;
}

Answer 1

Я не уверен, смогу ли я объяснить себя к вашему удовольствию, но я позволил себе поиграть с этим кодом и нашел несколько других похожих фрагментов со всего Интернета:

• Запись сортировки слиянием в PHP
• http://www.codecodex.com/wiki/Merge_sort#PHP

Что касается вашего кода, закомментировав возвращаемое значение более высоким уровням рекурсии было отказано в обновленных данных, поступающих с последующих / более низких уровней рекурсии. Другими словами, null было передано обратно в merging() вместо данных типа массива - что, конечно, не повторяется / не исчисляется.

Я также обнаружил, что ваш код слишком много для Мой мозг следовал, поэтому я сделал некоторые изменения, чтобы уменьшить раздувание кода и одноразовые переменные.

Код: ( Демо )

function mergeSort($array) {
    echo "array = " . json_encode($array) . "\n";
    $count = count($array);
    if ($count == 1) {
        return $array;
    }
    return merge(
        mergeSort(array_splice($array, 0, $count / 2)),
        mergeSort($array)  // use the leftovers
    );
}

function merge($half1, $half2) {
    do {
        $temp[] = $half1[0] < $half2[0] ? array_shift($half1) : array_shift($half2);
    } while(isset($half1[0], $half2[0]));
    return array_merge($temp, $half1, $half2);  // gather any potential remaining elements
}

$input = [4, 2, 7, 5, 3];
$input = mergeSort($input);
var_export($input);

Вывод:

array = [4,2,7,5,3]
array = [4,2]
array = [4]
array = [2]
array = [7,5,3]
array = [7]
array = [5,3]
array = [5]
array = [3]
array (
  0 => 2,
  1 => 3,
  2 => 4,
  3 => 5,
  4 => 7,
)

или с вашим вводом, вывод:

array = [4,2,7,5]
array = [4,2]
array = [4]
array = [2]
array = [7,5]
array = [7]
array = [5]
array (
  0 => 2,
  1 => 4,
  2 => 5,
  3 => 7,
)