IITD2011Interview

Question

#IITD_2011 which is better merge sort or heap. sort ?

Answer 1

if you have extra space you can go for merge sort. else you should have to remain happy with the heap sort . intuitively if you see, if an array is sorted  we are  to swap/assign a lot in merge sort but that's not the case in heap sort.you call heapify(A,i) you are not going to swap once also .

 

so better go for heap sort.....

Comments

Too much space

Answer 2

MergerSort is better because for larger datasets, mergesort works faster and is stable. Also it can be parallelized. As for Heapsort , sorting is not stable also there is a overhead of maintaining heap.

Answer 3

Merge sort is better

Reason- it always have same complexity irrespective of input , so easier to analyse. While that is not the case in heap sort.