Merge Sort Function

/* Author: Masuod Maldar, [email protected]
 * Originally Called: MergeSort (but is only the merge part)
 * UpdatedBy: J.B.Lamer, Date: 20070322
 *
 * $a1 and $a2 are presorted arrays (NOTE: they should be sorted)
 * a sorted array of both is returned (if arrays)
 * 
 * sorted array is returned otherwise
 * NOTE: there is no checking to see if $a1 and $a2 are arrays
 */
function merge( $a1, $a2 )
{	
	$sorted = array();
	$len1 = count($a1);
	$len2 = count($a2);
	
    $i = $j = 0;
	while ( $i < $len1 && $j < $len2 )
	{
		// if they are equal is doesn't matter which goes first
		if ( $a1[$i] < $a2[$j] )
		{	array_push($sorted,$a1[$i++]); }
		else
		{	array_push($sorted,$a2[$j++]); }
	}
	
	// which ever still has elements they are all greater
	while ( $i < $len1 )
	{	array_push($sorted,$a1[$i++]); }
	while ( $j < $len2 )
	{	array_push($sorted,$a2[$j++]); }
    return $sorted;
}


/* Author: J.B.Lamer, Date: 20070322
 *
 * mergesort is a recursive sort function that uses the merge() function
 *   to complete it's sort
 *
 * $array_to_sort is the array that needs sorting
 *   the keys are pulled and replaced with a normal numeric array
 * false is returned if $array_to_sort is not an array
 *   and true is returned otherwise
 * $lvl is an internal variable to track recursion so
 *   that checking isn't done every pass (leave at 0)
 */
function mergesort( &$array_to_sort, $lvl=0 )
{
	if ( $lvl == 0 )
	{
		if ( !is_array($array_to_sort) )
		{	return false; }
		$array_to_sort = array_values($array_to_sort);
	}
	
	// if the length is 1 then it's sorted
	if ( 1 < ($len = count($array_to_sort)) )
	{
		$mid = ceil($len/2);
		$i=0;
		$left = array();
		$right = array();
		
		// split up the array in to two pieces down the middle
		for ( $i=0; $i < $mid; $i++ )
		{	array_push( $left, $array_to_sort[$i] ); }
		for ( $i=$mid; $i < $len; $i++ )
		{	array_push( $right, $array_to_sort[$i] ); }
		
		// Call mergesort on each array and merge them
		// It will finally come out of recursion when arrays
		//   are only 1 or 0 and are sorted, and merge will sort
		//   smaller arrays until we are back here and they will both
		//   be sorted
		mergesort( $left, $lvl+1 );
		mergesort( $right, $lvl+1 );
		$array_to_sort = merge( $left, $right );		
	}
	return true;
}