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

?>

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. — Charles, Feb 22 '12 at 18:48
Check this site for more help : http://php.net/manual/en/array.sorting.php — Sam Arul Raj T, Feb 22 '12 at 18:49
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? — halfer, Feb 22 '12 at 18:50
Might be nice to include a link to what you're trying to do: http://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: http://stackoverflow.com/questions/680541/quick-sort-vs-merge-sort — Arend, Feb 22 '12 at 18:59
@Arend I was creating a merge sort purely for the basis of understanding it and to practise implementing one. — jweb, Feb 22 '12 at 19:41
@Charles 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. — Omnimike, May 22 '13 at 16:46
@Arend 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. — Ruben, Mar 03 '14 at 06:49

score 8 · Accepted Answer · answered Feb 22 '12 at 18:54

8

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.

answered Feb 22 '12 at 18:54

Juan

3,433
29
32

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. – Tom Granot Nov 29 '14 at 19:37

score 5 · Answer 2 · answered Feb 22 '12 at 18:53

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

What if the size of your array is odd? – marfis Mar 06 '15 at 11:36 — marfis, Mar 06 '15 at 11:36

score 4 · Answer 3 · answered Feb 22 '12 at 18:59

4

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

answered Feb 22 '12 at 18:59

Avanche

1,630
2
13
15

score 1 · Answer 4 · answered Nov 10 '17 at 23:17

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

score 1 · Answer 5 · answered Jul 10 '18 at 10:08

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

Leopoldo Sanczyk · Answer 6 · 2020-09-24T04:14:27.980

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.

The last line should be `foreach ($aux as $v) $a[$start++] = $v;` — chqrlie, Sep 23 '20 at 07:45
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);` — chqrlie, Sep 23 '20 at 07:52
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. — chqrlie, Sep 23 '20 at 07:57
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. — Leopoldo Sanczyk, Sep 24 '20 at 04:34
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 ;) — Leopoldo Sanczyk, Sep 24 '20 at 04:34

score 0 · Answer 7 · answered Feb 02 '17 at 16:38

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

score 0 · Answer 8 · answered Nov 23 '20 at 11:11

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

Writing merge sort in PHP

8 Answers8

Linked