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.

									public static void IntroSort(ref int[] data)
{
	int partitionSize = Partition(ref data, 0, data.Length - 1);

	if (partitionSize < 16)
	{
		InsertionSort(ref data);
	}
	else if (partitionSize > (2 * Math.Log(data.Length)))
	{
		HeapSort(ref data);
	}
	else
	{
		QuickSortRecursive(ref data, 0, data.Length - 1);
	}
}

private static void InsertionSort(ref int[] data)
{
	for (int i = 1; i < data.Length; ++i)
	{
		int 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;
			}
		}
	}
}

private static void HeapSort(ref int[] data)
{
	int heapSize = data.Length;

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

	for (int i = data.Length - 1; i > 0; --i)
	{
		int temp = data[i];
		data[i] = data[0];
		data[0] = temp;

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

private static void MaxHeapify(ref int[] data, int heapSize, int index)
{
	int left = (index + 1) * 2 - 1;
	int right = (index + 1) * 2;
	int 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)
	{
		int temp = data[index];
		data[index] = data[largest];
		data[largest] = temp;

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

private static void QuickSortRecursive(ref int[] data, int left, int right)
{
	if (left < right)
	{
		int q = Partition(ref data, left, right);
		QuickSortRecursive(ref data, left, q - 1);
		QuickSortRecursive(ref data, q + 1, right);
	}
}

private static int Partition(ref int[] data, int left, int right)
{
	int pivot = data[right];
	int temp;
	int i = left;

	for (int 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;
}

Example

									int[] data = new int[] { -1, 25, -58964, 8547, -119, 0, 78596 };
IntroSort(ref data);

Output