title: Writing merge sort in PHP
body: <p>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:</p>
  
  <blockquote>
    <p>Fatal error: Allowed memory size of 536870912 bytes exhausted (tried
    to allocate 35 bytes) in /Users/web/www/merge.php on line 39</p>
  </blockquote>
  
  <p>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.</p>
  
  <pre><code>&lt;?php
  
  $array = array(8,1,2,5,6,7);
  print_array($array);
  merge_sort($array);
  print_array($array);
  
  function merge_sort(&amp;$list){
      if( count($list) &lt;= 1 ){
          return $list;
      }
  
      $left =  array();
      $right = array();
  
      $middle = (int) ( count($list)/2 );
  
      // Make left
      for( $i=0; $i &lt; $middle; $i++ ){
          $left[] = $list[$i];
      }
  
      // Make right
      for( $i = $middle; $i &lt; count($list); $i++ ){
          $right[] = $list[$i];
      }
  
      // Merge sort left &amp; right
      merge_sort($left);
      merge_sort($right);
  
      // Merge left &amp; right
      return merge($left, $right);
  }
  
  function merge(&amp;$left, &amp;$right){
      $result = array();
  
      while(count($left) &gt; 0 || count(right) &gt; 0){
          if(count($left) &gt; 0 &amp;&amp; count(right) &gt; 0){
              if($left[0] &lt;= $right[0]){
                  $result[] = array_shift($left);
              } else {
                  $result[] = array_shift($right);
              }
          } elseif (count($left) &gt; 0){
              $result[] = array_shift($left);
          } elseif (count($right) &gt; 0){
              $result[] = array_shift($right);
          }
      }
  
      print_array($result);exit;
  
      return $result;
  }
  
  function print_array($array){
      echo "&lt;pre&gt;";
      print_r($array);
      echo "&lt;br/&gt;";
      echo "&lt;/pre&gt;";
  }
  
  ?&gt;
  </code></pre>