Merge Sort Recursive

Merge sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves.

									function Merge(&$data, $left, $mid, $right) {
	$n1 = $mid - $left + 1;
	$n2 = $right - $mid;

	for ($i = 0; $i < $n1; $i++)
		$L[$i] = $data[$left + $i];

	for ($j = 0; $j < $n2; $j++)
		$R[$j] = $data[$mid + 1 + $j];

	$i = 0;
	$j = 0;
	$k = $left;

	while ($i < $n1 && $j < $n2)
	{
		if ($L[$i] <= $R[$j])
		{
			$data[$k] = $L[$i];
			$i++;
		}
		else
		{
			$data[$k] = $R[$j];
			$j++;
		}

		$k++;
	}

	while ($i < $n1)
	{
		$data[$k] = $L[$i];
		$i++;
		$k++;
	}

	while ($j < $n2)
	{
		$data[$k] = $R[$j];
		$j++;
		$k++;
	}

	$L = null;
	$R = null;
}

function MergeSortRecursive(&$data, $left, $right) {
	if ($left < $right)
	{
		$m = $left + ($right - $left) / 2;

		MergeSortRecursive($data, $left, $m);
		MergeSortRecursive($data, $m + 1, $right);
		Merge($data, $left, $m, $right);
	}
}

Example

									$data = array(-1, 25, -58964, 8547, -119, 0, 78596);
MergeSortRecursive($data, 0, 6);

Output