5

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?

Henry Wang
  • 161
  • 2
  • 2
  • 14
  • 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. – Ahmed Hammad Nov 12 '18 at 19:42
  • "It depends" ;) See https://en.wikipedia.org/wiki/Sorting_algorithm. Note the section on "stability". There is no absolute, one size fits all answer to your question. – paulsm4 Nov 12 '18 at 19:43
  • https://stackoverflow.com/questions/2467751/quicksort-vs-heapsort – JHDev Nov 12 '18 at 19:46
  • 4
    @paulsm4 - 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. – rcgldr Nov 13 '18 at 03:41
  • 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. – amm98d Jul 04 '20 at 06:58

2 Answers2

12

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.

rcgldr
  • 27,407
  • 3
  • 36
  • 61
  • So in the end it depends on the system... – Henry Wang Nov 12 '18 at 21:10
  • @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. – rcgldr Nov 12 '18 at 21:29
  • 3
    @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](https://www.toptal.com/developers/sorting-algorithms) – paulsm4 Nov 13 '18 at 01:25
  • 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 @rcgldr – amm98d Jul 04 '20 at 07:16
  • 1
    @amm98d - 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. – rcgldr Jul 04 '20 at 09:24
0

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.

Deepam Gupta
  • 2,374
  • 1
  • 30
  • 33
Sandeepa
  • 3,457
  • 5
  • 25
  • 41
  • 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?" – Henry Wang Nov 12 '18 at 19:51
  • 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 – Sandeepa Nov 12 '18 at 19:59