Version: 1.0

Type: Function

Category: Algorithms

License: Other

Description: This function gets two sorted array and their's length ,then combine this two array in one and holds their sorted state. Currently this function mergging only two sorted (numeric,string) array and can develope to merge more . I welcome any sugesstion or comment about it.my E-mail address is : masuod_maldar@yahoo.com



/* Author: Masuod Maldar, masuod_maldar@yahoo.com
 * 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;
}