- 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] ← heap- size[A] - 15 MAX-HEAPIFY(A, 1) 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); } } |