Explanation of Merge Sorting with PHP

Question

Merge function working correctly.I have 2 queries in merge sort 1) I am not able to get why "merge" function calls third time(print execute) here when count==1 condition mets two times for both left and right together. 2) If I comment return $x then printing $x shows blank array third time otherwise $x show sorted array in third time why?

$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;
}

`merging()` is an odd choice for the method name because it is "splitting" or "halfing". I am still trying to understand what your strange recursive function is trying to accomplish. — mickmackusa, Apr 22 '20 at 07:36
@mickmackusa okay, could you please help me why third time merge function execute. — Anil Tomar, Apr 22 '20 at 07:39
@NigelRen First time merge run count==1 fulfill left=4,right=2 then second time count==1 fulfills and left=7,right=5 after why merge function execute when count==1 not fulfilling. — Anil Tomar, Apr 22 '20 at 07:52
@AnilTomar I've keep staring at your script thinking -- there's got to be a better way to do whatever you are trying to do. Here is some diagnostics: https://3v4l.org/ePo7H — mickmackusa, Apr 22 '20 at 07:59
After looking a bit more, it looks something like a bubble sort. It splits the list and then sorts each side, this in turn splits the list until there is only 1 item in the list. The results are then merged into a sorted list back up the chain. So each call is sorting each successively smaller list of items. — Nigel Ren, Apr 22 '20 at 08:09
@mickmackusa why the third time "execute" word echo when count==1 condition not satisfied. How it's getting possible third time merge($left,$right)calls? — Anil Tomar, Apr 22 '20 at 08:28
I think you are not understanding the behavior of recursion. The initial iteration doesn't "go away" once the recursive call is made; it is just delayed until all of the subsequent recursive processing is done. I don't know how to explain this to you -- which is why I didn't answer. See how in my demo, there is a `array ( 0 => 4, 1 => 2, 2 => 7, 3 => 5, )` at the start and at the end? — mickmackusa, Apr 22 '20 at 08:30
@mickmackusa thanks for your help but still didn't why initial iteration doesn't go away as according to logic count==1 mets two times. If possible any simple iteration function or reference link for this logic. — Anil Tomar, Apr 22 '20 at 16:11

mickmackusa · Answer 1 · 2020-04-22T22:38:33.230

I'm not sure if I'll be able to explain myself to your satisfaction, but I did indulge in having a play with this code and found some other similar snippets from around the web:

As for your code, by commenting out the return value, the higher levels of recursion were denied the updated data coming from the subsequent/lower levels of recursion. In other words, null was passed back to merging() instead of array-type data -- which of course is non-iterable/non-countable.

I also found your code to be too much for my brain to follow, so I made some changes to reduce the code bloat and single-use variables.

Code: (Demo)

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);

Output:

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,
)

or with your input, the output is:

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,
)

Explanation of Merge Sorting with PHP

1 Answers1