Intro Sort

Intro sort (a.k.a Introspective Sort) is hybrid sorting algorithm that provides both fast average performance and optimal worst-case performance. It begins with Quick sort and switches to Heap sort when the recursion depth exceeds a level based on the number of elements being sorted.

									function InsertionSort(&$data, $count) {
	for ($i = 1; $i < $count; $i++)
	{
		$j = $i;

		while ($j > 0)
		{
			if ($data[$j - 1] > $data[$j])
			{
				$data[$j - 1] ^= $data[$j];
				$data[$j] ^= $data[$j - 1];
				$data[$j - 1] ^= $data[$j];

				$j--;
			}
			else
			{
				break;
			}
		}
	}
}

function MaxHeapify(&$data, $heapSize, $index) {
	$left = ($index + 1) * 2 - 1;
	$right = ($index + 1) * 2;
	$largest = 0;

	if ($left < $heapSize && $data[$left] > $data[$index])
		$largest = $left;
	else
		$largest = $index;

	if ($right < $heapSize && $data[$right] > $data[$largest])
		$largest = $right;

	if ($largest != $index)
	{
		$temp = $data[$index];
		$data[$index] = $data[$largest];
		$data[$largest] = $temp;

		MaxHeapify($data, $heapSize, $largest);
	}
}

function HeapSort(&$data, $count) {
	$heapSize = $count;

	for ($p = ($heapSize - 1) / 2; $p >= 0; $p--)
		MaxHeapify($data, $heapSize, $p);

	for ($i = $count - 1; $i > 0; $i--)
	{
		$temp = $data[$i];
		$data[$i] = $data[0];
		$data[0] = $temp;

		$heapSize--;
		MaxHeapify($data, $heapSize, 0);
	}
}

function Partition(&$data, $left, $right) {
	$pivot = $data[$right];
	$temp;
	$i = $left;

	for ($j = $left; $j < $right; $j++)
	{
		if ($data[$j] <= $pivot)
		{
			$temp = $data[$j];
			$data[$j] = $data[$i];
			$data[$i] = $temp;
			$i++;
		}
	}

	$data[$right] = $data[$i];
	$data[$i] = $pivot;

	return $i;
}

function QuickSortRecursive(&$data, $left, $right) {
	if ($left < $right)
	{
		$q = Partition($data, $left, $right);
		QuickSortRecursive($data, $left, $q - 1);
		QuickSortRecursive($data, $q + 1, $right);
	}
}

function IntroSort(&$data, $count) {
	$partitionSize = Partition($data, 0, $count - 1);

	if ($partitionSize < 16)
	{
		InsertionSort($data, $count);
	}
	else if ($partitionSize >(2 * log($count)))
	{
		HeapSort($data, $count);
	}
	else
	{
		QuickSortRecursive($data, 0, $count - 1);
	}
}

Example

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

Output