Let us start with the heapsort algorithm:

heap_sort(int Arr[])
{
int heap_size = n;
build_maxheap(Arr);
for(int i = n; i >= 2 ; i--)
{
swap(Arr[1], Arr[i]);
heap_size = heap_size - 1;
heapify(Arr, 1, heap_size);
}
}

The build_maxheap() funnction has a standard implementation of O(n). The important part of the sorting is the for loop, which executes for n times. Inside that we have a swap method call and heapify method call. The heapify method is a standard walk through of complete binary tree. Hence, the complexity is O(log n)

T(n) = O(n) + n * O(log n) =…

Arunkumar Krishnan

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store