question about merge sort under php

Question

hello, i'v been trying to implement merge sort under php. but seems unsuccessful :( couldn't find source of error. any kind of help is very much appreciated!

function merge_sort(&$input, $start, $end) {
    if($start < $end) {
        $mid = (int) floor($start + $end / 2);
        merge_sort($input, $start, $mid);
        merge_sort($input, $mid + 1, $end);
        merge($input, $start, $mid, $end);
    } 
}

function merge(&$input, $p, $q, $r) { 
    $a = $q - $p + 1;
    $b = $r - $q;

    for($i = $p;$i <= $q;$i++) {
        $arr1[] = $input[$i];
    }

    for($i = $q+1;$i <= $r;$i++) {
        $arr2[] = $input[$i];
    }   

    $c = $d = 0;
    for($i = $p; $i <= $r; $i++) {
        $s = $arr1[$c];
        $t = $arr2[$d];

        if($a && (($s <= $t) || !$b)) { 
            $input[$i] = $s;
            $a--;$c++;
        } else if($b) {
            $input[$i] = $t;
            $b--;$d++;
        }
    } 
    return true;
}

here's the info xdebug throw back:

Fatal error: Maximum function nesting level of '100' reached, aborting! 

Answer 1

There is a maximum function nesting level of '100', and you have reached it. Your recursive function goes too deep.

Answer 2

Set

xdebug.max_nesting_level=500 

in my php.ini

Answer 3

From http://www.xdebug.org/docs/all%5Fsettings:

xdebug.max_nesting_level Type: integer, Default value: 100 Controls the protection mechanism for infinite recursion protection. The value of this setting is the maximum level of nested functions that are allowed before the script will be aborted.

You are going too deep in your recursive function triggering this xdebug error. Try raising this limit and see if that helps.

Also, here is an interesting article about recursion and PHP: http://www.alternateinterior.com/2006/09/tail-recursion-in-php.html

Answer 4

PHP is not a good language for recursive algorithms. From the manual:

It is possible to call recursive functions in PHP. However avoid recursive function/method calls with over 100-200 recursion levels as it can smash the stack and cause a termination of the current script.

If you need to do it in PHP, you'll probably have to find an iterative version of the algorithm. You've hit a hard-coded limit in the language.

Answer 5

To reach a nesting level of 100 on a merge sort, you would need to have an input array of size 2^100(about 1e30), which is impossible. I suspect your recursion is incorrect. For instance, you wrote $start + $end / 2 instead of ($start + $end) / 2.

Answer 6

Cosi dovrebbe funzionare!!!! www.dslpg.it

function merge ( &$a, $left,  $center, $right ) { //left = p   right = r  center = q
    $n1 = $center - $left + 1;
    $n2 = $right - $center;
    for ($i = 1; $i <= $n1; $i++) $L[$i] = $a[$left+$i-1];
    for ($i = 1; $i <= $n2; $i++) $R[$i] = $a[$center+$i];
    $L[$n1+1] = 99999;
    $R[$n2+1] = 99999; 
    $i = 1;
    $j = 1;
    for ($k = $left; $k <= $right; $k++) {
        if ($L[$i] <= $R[$j] ) {
            $a[$k] = $L[$i];
            echo $a[$k];
            $i++;
        }
        else {
            $a[$k] = $R[$j];
            echo $a[$k];
            $j++;
        }
    }
    return $a;
}
function merge_sort ( &$a, $left, $right ) { //left = p  right = r
    if ( $left < $right ) {
        $center = (int) floor(($left + $right) / 2 );

        merge_sort ($a, $left, $center);
        merge_sort ($a, $center+1, $right);
        merge ($a, $left, $center, $right);
    }
}
merge_sort ( $a, 1, $n );