TestBook Test Series: Algorithms - Sorting

Question

Answer 1

A. insertion sort - gives time complexity of O(n^2)

B. Quick sort - Ads the array is in reversed order, it is worst case for it, so time complexity O(n^2)

C. Merge sort - time complexity is O(nlogn), but takes additional time for unnecessary division.

D. Heap Sort - complexity O(nlogn). (Answer)

Comments

@sir plz give a reason???????

---

i have read that in best case for heap sort the constant factor for O(n.log n) is less than 1 ....so is it the reason why heap sort is better than merge sort and it also dont require auxillary space. but it is not stable sorting????

---

I think the reason is that no stack space is required for recursive calls.

Answer 2

Best in terms of complexity :
Time complexity filter out and we have choice of merge and heap sort.
Space complexity selects heap sort as best due to extra space required by merge sort.
So best is Heap sort.