# Cormen Edition 3 Exercise 6.4 Question 3 (Page No. 160)

23 views

What is the running time of HEAPSORT on an array $A$ of length $n$ that is already sorted in increasing order? What about decreasing order?

## Related questions

1
38 views
Show that the worst-case running time of HEAPSORT is $\Omega(n\lg\ n)$.
Argue the correctness of HEAPSORT using the following loop invariant: At the start of each iteration of the for loop of lines $2–5$,the subarray $A[1..i]$ is a max-heap containing the $i$ smallest elements of $A[1..n]$, and the subarray $A[i+1..n]$ contains the $n- i$ largest elements of $A[1..n]$, sorted.
HEAPSORT(A) 1 BUILD-MAX-HEAP(A) 2 for i = A.length down to 2 3 exchange A[1] with A[i] 4 A.heapsize=A.heapsize – 1 5 MAX-HEAPIFY(A,1) illustrate the operation of HEAPSORT on the array $A=\langle 5,13,2,25,7,17,20,8,4 \rangle$
Show that when all elements are distinct, the best-case running time of HEAPSORT is $\Omega(n\lg\ n)$.