Question

Which of the following desirable properties does a typical implementation of heap sort guarantee? (Select all that apply)

O (1) space complexity (when sorting an array)
O (n log n) worst-case time complexity
O Stability (relative ordering of values comparing as equal does not change)
O (n) best-case time complexity for already-sorted inputs

Answer 1

Heap sort guarantees O(1) space complexity and O(n log n) worst-case time complexity but does not ensure stability or a O(n) best-case time complexity for already-sorted inputs.

Step-by-step explanation:

The student has enquired about the properties of a typical implementation of heap sort. Heap sort is a comparison-based sorting algorithm that guarantees the following:

• 
  
• 
  

However, heap sort does not guarantee stability; if two elements are equal, their relative order may not be preserved in the sorted array. Also, heap sort does not have a O(n) best-case time complexity for already-sorted inputs, contrary to other algorithms like insertion sort which can perform better on sorted data. This is an important distinction as it affects decision-making when choosing the right sorting algorithm for a given problem set.