Quick sort and Merge sort algorithms written in PHP with explanations and pseudo code.

mergesort.php

<?php
  
  /*
  ** Merge sort algorithm
  * 
  * @author: Sven Anders Robbestad
  * 
  * These are algorithms I'm writing as part
  * of a course on Stanford called 
  * Algorithms: Design and Analysis by Tim Roughgarden
  *
  * Input: unsorted array
  * Output: sorted array
  * 
  * Steps:
  * Split the input array into two chunks
  * Sort the chunks recursively
  * Merge the chunks
  * 
  */
  
  /*
  Pseudo code for merge sort
  C= output array[length=n]
  A= 1st sorted array[length=n/2]
  B= 2nd sorted array[length=n/2]
  i=1
  j=1
  
  for k=1 to n
    if A[i] < B[i]
        C[k]==A[i]
        i++
    else B[j] < A[i]
        C[k] = B[j]
        j++
  end
  * 
  */
  
  /*
  ** Function declarations
  */
   
  function quickSort($input){
    if(empty($input)) return $input;
    $low=$high=array();
        for($i=1;$i<count($input);$i++){       
        if ($input[$i] <= $input[0]) {
            $low[]=$input[$i];
        } else {
            $high[]=$input[$i];
        }
      }
      return array_merge(quickSort($low), array($input[0]), quickSort($high));
  }
  
  function mergeArray ($A,$B){
     
      // Claim: Merge sort requires 6n log2n +6n operations
      // to sort n numbers
      
      $i=$j=0;
      $output=array();
      for($l=0;$l<(count($A)+count($B));$l++){
          if(!empty($B[$j]) && ($j>count($B) || ($i<count($A) && $A[$i]<$B[$j])))
            $output[$l]=$A[$i++];
          else if( $i>count($A) || $j<count($B))
            $output[$l]=$B[$j++];
          else
            $output[$l]=$A[$i++];
          
      }
       
      return $output;
  }
  
  function mergeSort($array){
      $chunks=array_chunk($array,(count($array)/2));
      
      // in case the input array is odd, we append the remaining data to the second unsorted array
      if(!empty($chunks[2])) $chunks[1]=array_merge($chunks[1],$chunks[2]);
      
      $ch1=quickSort($chunks[0]);
      $ch2=quickSort($chunks[1]);
      
      $result=mergeArray($ch1,$ch2);
      return $result;
  }
  
  /*
  ** Tests
  */
  
  $array=array(5,4,1,8,7,2,6,3);
  $result=mergeSort($array);
    
  // dump the result 
  foreach($result as $v) echo $v.PHP_EOL;