Time and Space Complexity of Heap Sort

Space Complexity: O(1)

Time Complexity: (HeapifyDown) O(logn)

Creating a maxHeap out of an array

Total nodes: n

Leaf nodes: n/2

For leaf nodes, we have to do zero operations.

Create a maxHeap out of array Time Complexity: O(n)

Time Complexity = O(n) + O(nlogn)

Total: O(nlogn)

Time Comparison with Other Sorts

Stable Sorting Algorithm

Sort the array by ‘age’

        
            [
                {name: Rahul, age: 20},
                {name: Akshay, age: 18},
                {name: Simran. age: 18},
                {name: Sachin, age: 30}
            ]
        
        

Sroted Array: [{Sachin}, {Rahul}, {Akshay}, {Simran}] (sorted in decreasing order)

Stable Algorithm: This algorithm ensures that the same value element maintain’s relative order.

.Sort in JavaScript

It ensures stable sorting.