question about merge sort under php

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, $s开发者_如何学编程tart, $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! 

---

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.

---

Set

xdebug.max_nesting_level=500 

in my php.ini

---

Here's my working solution, feel free to compare...

/**
 * @param array $items array to sort
 * @param int   $l     left index (defaults to 0)
 * @param int   $r     right index (defaults to count($items)-1)
 */
function mergeSort(&$items, $l = 0, $r = null)
{
    if (!isset($r)) {
        $r = count($items) - 1;
    }

    if ($l < $r) {
        $m = floor(($r - $l) / 2) + $l;
        mergeSort($items, $l, $m);
        mergeSort($items, $m + 1, $r);
        merge($items, $l, $m, $r);
    }
}

/**
 * @param array $items array to merge
 * @param int   $l     left index
 * @param int   $m     middle index
 * @param int   $r     right index
 */
function merge(&$items, $l, $m, $r)
{
    $itemsA = array_slice($items, $l, $m + 1 - $l);
    $itemsB = array_slice($items, $m + 1, ($r + 1) - ($m + 1));

    $a = 0;
    $aCount = count($itemsA);
    $b = 0;
    $bCount = count($itemsB);

    for ($i = $l; $i <= $r; $i++) {
        if ($a < $aCount && ($b == $bCount || $itemsA[$a] <= $itemsB[$b])) {
            $items[$i] = $itemsA[$a++];
        } else {
            $items[$i] = $itemsB[$b++];
        }
    }
}

$items = array(5,3,6,1,2,3,9,10,7,2,4,8);
mergeSort($items);
echo implode(',', $items) . "\n";

Outputs:

1,2,2,3,3,4,5,6,7,8,9,10

---

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

---

From http://www.xdebug.org/docs/all_settings:

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

---

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.

---

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