• 0

Running time of heapsort for a sorted array in ascending/descending order
  • timecomplexity
  • heapsort
  • sorting
  • array
  •   
    subscribe
  • Posted: 7 years ago
  • Updated: 6 years ago
  • Edit
  • answers (1)
  • views (16306)

What is the running time of heapsort on an array A of length n that is already sorted in ascending order? How about the descending order?


Posted Answers

  • Posted: 7 years ago
  • 0 0
  • Edit

  • When the input array A is sorted in ascending order, at each iteration, each call of Max_heapify(A,1) will still take \( O(logn) \) time.
    Hence the running time of heapsort will be \( O(nlogn) \) for n elements in the array.

  • When the input array is sorted in descending order, heapsort will still take \( O(nlogn) \) time since the cost of Max_heapify does not change.

    • You need to Sign In to post your solution.