Merge Sort Iterative

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 MergeSortIterative(&$data, $count) {
	for ($currentSize = 1; $currentSize <= $count - 1; $currentSize = 2 * $currentSize)
	{
		for ($leftStart = 0; $leftStart < $count - 1; $leftStart += 2 * $currentSize)
		{
			$mid = $leftStart + $currentSize - 1;
			$rightEnd = min($leftStart + 2 * $currentSize - 1, $count - 1);

			Merge($data, $leftStart, $mid, $rightEnd);
		}
	}
}

Example

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

Output