Cocktail Shaker Sort

Cocktail shaker sort, also known as bidirectional bubble sort, cocktail sort, shaker sort, ripple sort, shuffle sort, or shuttle sort, is a variation of bubble sort that is both a stable sorting algorithm and a comparison sort. The algorithm differs from a bubble sort in that it sorts in both directions on each pass through the list. This sorting algorithm is only marginally more difficult to implement than a bubble sort, and solves the problem of turtles in bubble sorts. It provides only marginal performance improvements, and does not improve asymptotic performance; like the bubble sort.

									function Swap(&$a, &$b)
{
	$a ^= $b;
	$b ^= $a;
	$a ^= $b;
}

function CocktailSort(&$data)
{
	$count = count($data);
	
	while (true)
	{
		$flag;
		$start = array(1, $count - 1);
		$end = array($count, 0);
		$inc = array(1, -1);

		for ($it = 0; $it < 2; ++$it)
		{
			$flag = true;

			for ($i = $start[$it]; $i != $end[$it]; $i += $inc[$it])
			{
				if ($data[$i - 1] > $data[$i])
				{
					Swap($data[$i - 1], $data[$i]);
					$flag = false;
				}
			}

			if ($flag)
				return;
		}
	}
}

Example

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

Output