Writing merge sort in PHP

Question

I have tried to write a basic merge sort in PHP involving a small array, yet the problem is it takes about a minute or so to execute, and returns:

Fatal error: Allowed memory size of 536870912 bytes exhausted (tried to allocate 35 bytes) in /Users/web/www/merge.php on line 39

Does anyone have an idea where the code might be going wrong (if at all)? I've been staring at this for a good hour now.

<?php

$array = array(8,1,2,5,6,7);
print_array($array);
merge_sort($array);
print_array($array);

function merge_sort(&$list){
    if( count($list) <= 1 ){
        return $list;
    }

    $left =  array();
    $right = array();

    $middle = (int) ( count($list)/2 );

    // Make left
    for( $i=0; $i < $middle; $i++ ){
        $left[] = $list[$i];
    }

    // Make right
    for( $i = $middle; $i < count($list); $i++ ){
        $right[] = $list[$i];
    }

    // Merge sort left & right
    merge_sort($left);
    merge_sort($right);

    // Merge left & right
    return merge($left, $right);
}

function merge(&$left, &$right){
    $result = array();

    while(count($left) > 0 || count(right) > 0){
        if(count($left) > 0 && count(right) > 0){
            if($left[0] <= $right[0]){
                $result[] = array_shift($left);
            } else {
                $result[] = array_shift($right);
            }
        } elseif (count($left) > 0){
            $result[] = array_shift($left);
        } elseif (count($right) > 0){
            $result[] = array_shift($right);
        }
    }

    print_array($result);exit;

    return $result;
}

function print_array($array){
    echo "<pre>";
    print_r($array);
    echo "<br/>";
    echo "</pre>";
}

?>

Bold

While this isn't your problem, be aware that PHP has a maximum recursion limit of 100. You may eventually hit this limit when given a large enough array. – Chrisom

Check this site for more help : php.net/manual/en/array.sorting.php – Discriminate

I'm not familiar with the algorithm, but I'd suggest doing some echo/exits at various points in the code, to see if you're getting intermediate steps correctly? – Splendor

Might be nice to include a link to what you're trying to do: en.wikipedia.org/wiki/Merge_sort. I would personally use php's native (written in C) sort algorithm - I think php code will be less efficient then php's native quicksort methods. An explanaition why quicksort will be better then merge sort (besides the obvious native vs PHP code can be found here: https://mcmap.net/q/179562/-quick-sort-vs-merge-sort-duplicate – Therrien

@Therrien I was creating a merge sort purely for the basis of understanding it and to practise implementing one. – Bold

@Chrisom Even if that were true you would need an array of about 2^100 (1.268 x 10^30) elements before you hit the recursion limit. You would run out of memory long before that ever happened. – Georgia

@Therrien I know this is a really old thread, but I still felt compelled to comment on your remark. Sure, in many instances quicksort will be more efficient than merge sort, but it all depends on the situation, environment and other factors. You can't simply say that algorithm A is always better than algorithm B. There's different algorithms for sorting for a good reason. – Malamut

Answer 1

In your merge function, you call count on right instead of $right. PHP assumes this is a string constant (at least in 5.3.9) and when casted into an array that always has one element. So count(right) is always one, and you never exit the first merge.

Hube

I'm sorry to say, but this does not work well. The exit at the end there kind of leaves you with the minimum-sized array, of 2 terms. If you omit it, it just throws all the arrays at you. There needs to be some merging of the arrays somewhere in there. – Deerdre

Answer 2

Try this approach. Instead of shifting it, slice.

Also, for in while loop for the merge function, you need to do an and && comparison instead of ||

function mergeSort($array)
{
    if(count($array) == 1 )
    {
        return $array;
    }

    $mid = count($array) / 2;
    $left = array_slice($array, 0, $mid);
    $right = array_slice($array, $mid);
    $left = mergeSort($left);
    $right = mergeSort($right);

    return merge($left, $right);
}


function merge($left, $right)
{
    $res = array();

    while (count($left) > 0 && count($right) > 0)
    {
        if($left[0] > $right[0])
        {
            $res[] = $right[0];
            $right = array_slice($right , 1);
        }
        else
        {
            $res[] = $left[0];
            $left = array_slice($left, 1);
        }
    }

    while (count($left) > 0)
    {
        $res[] = $left[0];
        $left = array_slice($left, 1);
    }

    while (count($right) > 0)
    {
        $res[] = $right[0];
        $right = array_slice($right, 1);
    }

    return $res;
}

Blat

What if the size of your array is odd? – Moresque

Answer 3

Have a look at this, the algorithm is already implemented, using array_push and array splice instead of just array_shift.

http://www.codecodex.com/wiki/Merge_sort#PHP

Kolomna

Answer 4

I implement merge sort this way

function mergeSort($Array)
{
    $len = count($Array);
    if($len==1){
        return $Array;
    }
    $mid = (int)$len / 2;
    $left = mergeSort(array_slice($Array, 0, $mid));
    $right = mergeSort(array_slice($Array, $mid));
    return merge($left, $right);
}

function merge($left, $right)
{


    $combined = [];
    $totalLeft = count($left);
    $totalRight = count($right);
    $rightIndex = $leftIndex=0;
    while ($leftIndex < $totalLeft && $rightIndex < $totalRight) {
        if ($left[$leftIndex] > $right[$rightIndex]) {
            $combined[]=$right[$rightIndex];
            $rightIndex++;
        }else {
            $combined[] =$left[$leftIndex];
            $leftIndex++;
        }
    }
    while($leftIndex<$totalLeft){
        $combined[]=$left[$leftIndex];
        $leftIndex++;
    }
    while ($rightIndex<$totalRight){
        $combined[] =$right[$rightIndex];
        $rightIndex++;
    }
    return $combined;
}

Norwich

Answer 5

Here is the class in PHP to implement the Merge Sort -

            <?php
            class mergeSort{
                public $arr;
                public function __construct($arr){
                    $this->arr = $arr;
                }

                public function mSort($l,$r){
                    if($l===null || $r===null){ 
                        return false;
                    }
                    if ($l < $r)
                    {
                        // Same as ($l+$r)/2, but avoids overflow for large $l and $r
                        $m = $l+floor(($r-$l)/2);

                        // Sort first and second halves
                        $this->mSort($l, $m);
                        $this->mSort($m+1, $r);

                        $this->merge($l, $m, $r);
                    }
                }

                // Merges two subarrays of $this->arr[]. First subarray is $this->arr[$l..$m]. Second subarray is $this->arr[$m+1..$r]
                public function merge($l, $m, $r)
                {
                    if($l===null || $m===null || $r===null){    
                        return false;
                    }

                    $n1 = $m - $l + 1;
                    $n2 =  $r - $m;

                    /* create temp arrays */
                    $L=array();
                    $R=array();

                    /* Copy data to temp arrays $L[] and $R[] */
                    for ($i = 0; $i < $n1; $i++)
                        $L[$i] = $this->arr[$l + $i];

                    for ($j = 0; $j < $n2; $j++)
                        $R[$j] = $this->arr[$m + 1+ $j];

                    /* Merge the temp arrays back into $this->arr[$l..$r]*/
                    $i = 0; // Initial index of first subarray
                    $j = 0; // Initial index of second subarray
                    $k = $l; // Initial index of merged subarray
                    while ($i < $n1 && $j < $n2)
                    {
                        if($L[$i] <= $R[$j])
                        {
                            $this->arr[$k] = $L[$i];
                            $i++;
                        }
                        else
                        {
                            $this->arr[$k] = $R[$j];
                            $j++;
                        }
                        $k++;
                    }

                    /* Copy the remaining elements of $L[], if there are any */
                    while($i < $n1)
                    {
                        $this->arr[$k] = $L[$i];
                        $i++;
                        $k++;
                    }

                    /* Copy the remaining elements of $R[], if there are any */
                    while($j < $n2)
                    {
                        $this->arr[$k] = $R[$j];
                        $j++;
                        $k++;
                    }
                }
            }

            $arr = array(38, 27, 43, 5, 9, 91, 12);
            $obj = new mergeSort($arr);
            $obj->mSort(0,6);
            print_r($obj->arr);
            ?>

Millford

Answer 6

I was looking for a optimized Mergesort algorithm in PHP. There are 5 algorithms in the answers, so I tested those, and mine too. Using PHP 7.2.7, these are the times:

Sorting 1000 random numbers:

• Avanche 1 0.0396 seconds
• Avanche 2 0.0347 seconds
• Kartik 0.0291 seconds
• Kripa 0.0282 seconds
• Samuel 0.0247 seconds
• Mine 0.0144 seconds

Sorting 10 random numbers:

• Avanche 1 0.000222 seconds
• Kartik 0.000216 seconds
• Kripa 0.000159 seconds
• Avanche 2 0.000144 seconds
• Samuel 0.000128 seconds
• Mine 0.000098 seconds

So, although I encourage to whom read it to make it faster (that was I was looking for, and I believe it can be done), I let you my implementation too, cause seems to be faster than the other answers:

//This function needs start and end limits
function mergeSortRec(&$a,$start,$end){
  if($start<$end){
    $center=($start+$end)>>1; //Binary right shift is like divide by 2
    mergeSortRec($a, $start, $center);
    mergeSortRec($a, $center+1, $end);
    //Mixing the 2 halfs
    $aux=array();
    $left=$start; $right=$center;
    //Main loop
    while($left<$center && $right<=$end){
      if($a[$left]<$a[$right]){
        $aux[]=$a[$left++];
      }else{
        $aux[]=$a[$right++];
      }
    }
    //Copy the rest of the first half
    while($left<$center) $aux[]=$a[$left++];
    //Copy the rest of the second half
    while($right<=$end) $aux[]=$a[$right++];
    //Copy the aux array to the main array
    foreach($aux as $v) $a[$start++]=$v;
  }
}
//This is the function easier to call
function mergeSort(&$a) {
  mergeSortRec($a,0,count($a)-1);
}

If you post a new answer, let me a comment to test it and add it.

---

Edit: I did some new optimizations, for those looking for a better implementation.

Anamorphoscope

The last line should be foreach ($aux as $v) $a[$start++] = $v; – Magnuson

You might also want to test if $center = ($start + $end) >> 1; or $center = (int)(($start + $end) / 2); is more efficient than $center = floor(($start + $end) / 2); – Magnuson

Another idea: you could use a separate function mergeSort_rec without default argument values nor the test $end=$end??count($a)-1; and call that from mergeSort(). Considering $end as excluded produces cleaner and simpler code. – Magnuson

Thanks @chqrlie. You are right, I should apply some optimizations here, instead of waiting for other answers. The binary shift is ever a good one, it made the algorithm run 10% faster (didn't try the int cast). Spliting the function in recursive and non recursive calls, made it run even 5% faster. And avoiding the mix() call, another 5% more. So I updated the code with those changes. – Anamorphoscope

Perhaps we could add some more less obvious tweeks later and keep it updated. I remember there is one, that alternate between 2 arrays and avoids creating and destroying the aux array, for example, but all takes time. Let's wait for new encouragements later. For the moment, thanks for yours ;) – Anamorphoscope

Answer 7

Your merge sort accepts a list by reference

function merge_sort(&$list)

So you need to assign it the new merged and sorted list. So instead of

return merge($left, $right);

do

$list = $this->merge($left, $right);

That should do it, just remove the exit and fix the count variable

Sententious

Answer 8

MergeSort in PHP

<?php 
class Solution 
{
    function mergeSort(&$arr)
    {
        if(count($arr) > 1) {
            $mid = floor(count($arr)/2);
            
            $left = array_slice($arr, 0, $mid);
            $right = array_slice($arr, $mid);

            $this->mergeSort($left);
            $this->mergeSort($right);

            // Merge the results.
            $i = $j = $k = 0;
            while(($i < count($left)) && ($j < count($right))) {
                if($left[$i] < $right[$j]) {
                    $arr[$k] = $left[$i];
                    $i++;
                } else {
                    $arr[$k] = $right[$j];
                    $j++;
                }
                $k++;
            }

            while($i < count($left)) {
                $arr[$k] = $left[$i];
                $i++;
                $k++;
            }

            while($j < count($right)) {
                $arr[$k] = $right[$j];
                $j++;
                $k++;
            }
        }
    }
}

$s = new Solution();
$tmp = [12, 7, 11, 13, 5, 6, 7];
$s->mergeSort($tmp);
print_r($tmp);

Commove