Heap Sort

Heap sort is a comparison based sorting algorithm. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining element.

									public 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);
	}
}

Example

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

Output