Foundations‎ > ‎Algorithms‎ > ‎Sorting‎ > ‎

Heapsort

- Time Complexity -

O(n lg n)

- Pseudocode -

HEAPSORT(A)
1  BUILD-MAX-HEAP(A)
2  for i ← length[a] downto 2
3    do exchange A[1] ↔ A[i]
4      heap-size[A] ← heap-size[A] - 1
5      MAX-HEAPIFY(A, 1)

Note that in the implementation of heap via an array, the first node of the array is not used. See implementation of maxHeapify.
void heapSort(int *arr, int length)
{
	int lastElem = length - 1;
 
	while (lastElem > 0)
	{
		// swap the first and last elements
		int tmp = arr[lastElem];
		arr[lastElem] = arr[1];
		arr[1] = tmp;
 
		// correct the heap and remove one from the length
		maxHeapify(arr, lastElem--, 1);
	}
}