Please explain briefly

#1

what is the reason behind that merge sort is not better than heap sort ,I know that this is not a stable sort but I want to know other reason also…

#2

The merge sort is slightly faster than the heap sort for larger sets, but it requires twice the memory of the heap sort because of the second array.

#3

Both sorting algorithms have a worst case complexity of O(nlogn). However, one cannot simply say that one sorting algorithm is better than the other without looking at the scenario. If the data sets are small, the difference in time will be negligible to none, but when the data sets are large, as is the case in several competitive programming challenges, you need to choose the algorithm that best suits your scenario.

  1. Quick sort. For random data, this algorithm tends to partition the data set into two similarly sized pieces, placing one item in its final position, and the smaller items on one side and larger items on the other side. This means that in terms of locality, once we have a piece that fits in memory, locality is exploited until this piece is fully sorted. Thus, apart from the log(N) complexity of the algorithm, this method exploits locality quite reasonably.
  2. Heap sort. This method uses a heap that may be traversed randomly depending on the characteristics of the data. This is not really local, as the heap is touched all-over when the items find their place in the heap and other items are pulled up, leading to a poor locality if the heap does not fit in memory.
  3. Merge Sort. This is used when several runs (pieces of the data) are already sorted. The locality of the method comes from the fact that each run is traversed sequentially, thus, locality is exploited reasonably. Also, the heap used to sort is R Log® size for R being the number of runs to be sorted, which keeps locality reasonably well if the heap fits in memory.

Summing up, although Merge sort is a method that sorts pre-sorted sets of data, and Heap sort and Quick sort, sort generic unsorted data sets, Quick sort is best in preserving locality compared to many other methods, and Merge sort is very good for pre-sorted sets.

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.