Heap Sort Time Complexity

Consider the below figure and suppose that The heapsort technique is performed to an n-element array A. The method is divided into two phases for better understanding, and the complexity of each phase is evaluated independently.

Fig. 01: Data array 'A' of n-length.

First Phase: Now consider that 'H' is a heap for finding the complexity of heapsort. Take note that the number of comparisons required to locate the suitable location of a new member ITEM in 'H' cannot exceed the depth of the 'H' heap.

The heap H's depth is totally restricted by log₂m, where m is the number of items in the heap 'H'.

As a result, the total number of first_phase(n) comparisons required to insert the n items of the data array A into 'H' is constrained as follows:

first_phase(n) = n log₂ n

So, at the last, the first phase time complexity is proportional to n log₂ n.

Second Phase: Assume that the heap 'H' is totally free with m elements, that the left and right subtrees of 'H' are heaps, and that 'L' is the root of 'H'. Re-heaping employs four comparisons to shift the node 'L' one step down the tree 'H'.

Fig. 02: The heap 'H' with 'L' root and Child.

Because the depth of H can not exceed log₂ m, re-heaping employs no more than four log₂, m comparisons to locate the right location of L in the tree H. Are you thinking, what is the 'm'? Don't worry. The m represents the number of items in the heap 'H'.

This indicates that the total number second_phase(n) of comparisons required to delete the n elements of A from the heap 'H', requiring re-heaping n times, is constrained as follows:

second_phase(n) = 4n log₂ n

Ok. Finally, we get the second phase of time complexity. We can say that the time complexity of the second phase for the heap sort is proportional to n log₂ n.