Heap Sort (2016)

Mechanism

Build a Max-Heap from the input array (heapify) — O(n)
Repeatedly: swap the root (maximum element) with the last element of the heap, reduce heap size by 1, and "sift down" (heapify) the new root — repeat n-1 times

Pseudocode

HEAP_SORT(arr):
  BUILD_MAX_HEAP(arr)
  FOR i = n-1 DOWNTO 1:
    SWAP(arr[0], arr[i])
    HEAPIFY(arr, 0, i)  // restore heap property on reduced heap

Complexity

Time: O(n log n) in all cases (best, average, worst) — like Merge Sort, no worst-case degradation
Space: O(1) — in-place, unlike Merge Sort's O(n) — this is Heap Sort's key advantage
Not stable

Heap Sort vs Merge Sort vs Quick Sort (the classic 3-way comparison)

Algorithm	Worst-case Time	Space	Stable?
Merge Sort	O(n log n)	O(n)	Yes
Quick Sort	O(n²)	O(log n)	No
Heap Sort	O(n log n)	O(1)	No

Exam Angle

Heap Sort is the answer whenever a question asks for an algorithm with guaranteed O(n log n) AND O(1) space — it's the only one of the three offering both. Requires understanding of the Heap data structure (complete binary tree stored as array) as a prerequisite.

📌 Sample & Repeated FPSC Questions (2016–2026)

2016, Paper I, Q5(c) (6 marks) — Draw the array A = {8, 14, 2, 26, 10, 12, 16, 28, 20, 7} as a binary tree, apply Build-Max-Heap, then show the Heap-Sort execution by rewriting the array after each iteration.

Build-Max-Heap (heapify from last internal node, index 4, down to 0):

Start:            [8, 14, 2, 26, 10, 12, 16, 28, 20, 7]
i=4 (val 10): child 7          → 10>7, no change
i=3 (val 26): children 28,20   → swap with 28 → [8,14,2,28,10,12,16,26,20,7]
i=2 (val 2):  children 12,16   → swap with 16 → [8,14,16,28,10,12,2,26,20,7]
i=1 (val 14): children 28,10   → swap with 28, then sift 14 down past 26
                                → [8,28,16,26,10,12,2,14,20,7]
i=0 (val 8):  children 28,16   → swap with 28, sift 8 down past 26, then past 20
                                → [28,26,16,20,10,12,2,14,8,7]

Final Max-Heap (array + tree):

Array: [28, 26, 16, 20, 10, 12, 2, 14, 8, 7]

              28
           /      \
         26        16
        /  \      /  \
      20   10   12    2
     /  \
   14    8
   /
  7

Heap-Sort execution (swap root with last live element, shrink heap by 1, sift-down new root — array shown after each iteration, sorted tail growing on the right):