4. Explain Heapsort with example
Answer:
Two Stages:
Stage 1 (Build Heap): Construct a heap from the input array. Time: O(n)
Stage 2 (Sort): Delete the maximum (root) n−1 times and place it at the end of the array.
Sorting array [2, 9, 7, 6, 5, 8] using Heapsort.
Time Analysis
Let C(n) = total comparisons in second stage:
C(n) ≤ 2 log₂(n−1) + 2 log₂(n−2) + … + 2 log₂(1)
≤ 2(n−1) log₂(n−1)
∈ O(n log n)
Final Time Complexity of Heapsort:
O(n) + O(n log n) = O(n log n)
- Worst-case and average-case: O(n log n)
- In-place sort: No extra space needed.
- Slower than quicksort, but comparable to mergesort in performance.