Merge Sort Function

By jayon crow
on March 22, 2007

Version: 1.0

Type: Function

Category: Algorithms

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 : [email protected]

```/* 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;
}
```
﻿