<?php

/*
 *
 * @author: barce@codebelay.com
 * @date:   18 June 2008
 *
 * This is an implementation of mergesort in PHP.
 * 
 */
// MergeSort

// $a_set = array(53, 7, 22, 1, 8, 12, 52, 30, 42);
$a_set = array(53,7,8,22,16);
$a_sorted = mergesort($a_set);
print_r($a_sorted);

function mergesort($a_set) {

	$end = count($a_set);
	if (count($a_set) <= 1) {
		return $a_set;
	}
	$middle = round(count($a_set) / 2);

	for($i = 0; $i < $middle; $i++) {
		$left[] = $a_set[$i];
	}
	for($i = $middle; $i < $end; $i++) {
		$right[] = $a_set[$i];
	}

	print_r($left);
	print_r($right);
	$left   = mergesort($left);
	$right  = mergesort($right);
	return merge($left, $right);
}

function merge($left, $right) {
	while ((count($left) > 0) && (count($right) > 0)) {
		if ($left[0] <= $right[0]) {
			$result[] = $left[0];
			array_shift($left);
		} else {
			$result[] = $right[0];
			array_shift($right);
		}
	}

	if (count($left) > 0) {
		foreach ($left as $item) {
			$result[] = $item;
		}
	}

	if (count($right) > 0) {
		foreach ($right as $item) {
			$result[] = $item;
		}

	}
	print "---[result: start]---\n";
	print_r($result);
	print "---[result: end]---\n";
	return $result;
}


?>