Heap Sort vs Merge Sort in Speed [duplicate]

Question

Which algorithm is faster when iterating through a large array: heap sort or merge sort? Why is one of these algorithms faster than the other?

Sid

Generally speaking, both has the same complexity of O(n lg(n) ), which is the best thing you can get from a comparison-based sorts .. and each of them can be faster on specific occasions, depending on the application. – Slipover

"It depends" ;) See en.wikipedia.org/wiki/Sorting_algorithm. Note the section on "stability". There is no absolute, one size fits all answer to your question. – Freethinker

https://mcmap.net/q/181082/-quicksort-vs-heapsort – Hyperthermia

@Freethinker - duplicate question link is about heap sort versus quicksort, while this question is about heap sort versus merge sort. It needs a different link or it needs to unmarked as a duplicate. – Middlesworth

This is not a duplicate post. The post linked to be the duplicate is Heap Sort vs "Quick Sort", where as this one is Heap Sort vs "Merge Sort". Unless Quick Sort and Merge Sort are different names for the same thing (which they are not), this post should be reopened. – Bomarc

Answer 1

Although time complexity is the same, the constant factors are not. Generally merge sort will be significantly faster on a typical system with a 4 or greater way cache, since merge sort will perform sequential reads from two runs and sequential writes to a single merged run. I recall a merge sort written in C was faster than an optimized heap sort written in assembly.

One issue is that heap sort swaps data, that's two reads and two writes per swap, while merge sort moves data, one read and one write per move.

The main drawback for merge sort is a second array (or vector) of the same size as the original (or optionally 1/2 the size of the original) is needed for working storage, on a PC with 4 GB or more of RAM, this usually isn't an issue.

On my system, Intel 3770K 3.5 ghz, Windows 7 Pro 64 bit, Visual Studio 2015, to sort 2^24 = 16,777,216 64 bit unsigned integers, heap sort takes 7.98 seconds while bottom up merge sort takes 1.59 seconds and top down merge sort takes 1.65 seconds.

Middlesworth

So in the end it depends on the system... – Sid

@HenryWang - I updated my answer to note that heap sort swaps (2 reads 2 writes per swap), while merge sort moves (1 read, 1 write per move). Note that heap sort is more than 4 times as slow on my system. – Middlesworth

@Henry Wang: Q: So in the end it depends on the system. A: NOOO!!!!! It actually depends upon MANY things, INCLUDING system constraints (like memory), set order (partially sorted?), etc. etc. SUGGESTION: look here for some graphical comparisions Sorting algorithm animations – Freethinker

This suggests that irrespective of the system specs, merge sort will always perform better or at least the same as heap sort will do, as far as time complexity is concerned. I wrote Python code for both and I found results that contradict this. I checked both of them for arrays of sizes: 10,100,1000,10000,100000,1000000. I found that the heap sort code performs exceptionally better in all cases as compared to merge sort. For example, for the array of size 1000000, heap sort took 3.68 seconds while merge sort took 15.05 seconds. Could someone please provide some clarity on this @Middlesworth – Bomarc

@Bomarc - python is not good for time comparisons, due to the overhead of an interpretive language. A merge sort of an array of 1,000,000 32 bit integers in C++ takes about 0.08 seconds on my system, while a heap sort takes 0.10 seconds, only a bit slower. Increasing array size to 10,000,000, merge sort 0.88 seconds, heap sort 2.63 seconds. – Middlesworth

Answer 2

Both sort methods have the same time complexity, and are optimal. The time required to merge in a merge sort is counterbalanced by the time required to build the heap in heapsort. The merge sort requires additional space. The heapsort may be implemented using additional space, but does not require it. Heapsort, however, is unstable, in that it doesn't guarantee to leave 'equal' elements unchanged. If you test both methods fairly and under the same conditions, the differences will be minimal.

Hussein

I understand your point in the extra time in merging and creating the heap for the two respective sorts. What do you mean when you say "additional space?" – Sid

Merge sort could take more space than the original array, if it allocates both halves of the array in merge sort before making the recursive calls to itself – Hussein