Menu
What are are the relative advantages of the three in terms of the number of comparisons performed and the amount of memory required by the algorithms. Which of them is their running time guaranteed?
459
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.
Merge sort is more efficient and works faster than quick sort in case of larger array size or datasets. Quick sort is more efficient and works faster than merge sort in case of smaller array size or datasets.
Heapsort is typically somewhat slower than quicksort, but the worst-case running time is always Θ(nlogn). Quicksort is usually faster, though there remains the chance of worst case performance except in the introsort variant, which switches to heapsort when a bad case is detected.
Advantages of Heap Sort It is efficient for sorting a large number of elements. This implies that no other sorting algorithms can perform better in comparison. Memory usage is minimal. In contrast, the Merge Sort algorithm requires more memory space.
I think Wikipedia's coverage of this is pretty thorough and answers all your questions. The comparison table shows the best, average and worst-case performance, the memory usage, and other characteristics like stability.
81
This is easily answered by looking at Wikipedia...:
http://en.wikipedia.org/wiki/Sorting_algorithm
If you are unsure how to look for the "guaranteed" runtime then you're looking for the worst case.
36
If you want a visual explanation, this classic animation film called Sorting Out Sorting was made by a University of Toronto CS group in the 1980s. It is worth the watch, covering the three sort types and scenarios where they work best (and also not so well) — and why.
45
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
