Heap Sort vs Merge Sort in Speed [duplicate]
This question already has an answer here:
Quicksort superiority over Heap Sort
5 answers
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?
java sorting mergesort heapsort
asked Nov 12 at 19:40
Henry Wang
358
marked as duplicate by paulsm4, Community♦ Nov 13 at 1:30
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
This question already has an answer here:
Quicksort superiority over Heap Sort
5 answers
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?
java sorting mergesort heapsort
asked Nov 12 at 19:40
Henry Wang
358
marked as duplicate by paulsm4, Community♦ Nov 13 at 1:30
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
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 at 19:42
"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.
– paulsm4
Nov 12 at 19:43
stackoverflow.com/questions/2467751/quicksort-vs-heapsort
– esprittn
Nov 12 at 19:46
1
@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 at 3:41
add a comment |
This question already has an answer here:
Quicksort superiority over Heap Sort
5 answers
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?
java sorting mergesort heapsort
asked Nov 12 at 19:40
Henry Wang
358
This question already has an answer here:
Quicksort superiority over Heap Sort
5 answers
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?
This question already has an answer here:
Quicksort superiority over Heap Sort
5 answers
java sorting mergesort heapsort
java sorting mergesort heapsort
asked Nov 12 at 19:40
Henry Wang
358
asked Nov 12 at 19:40
Henry Wang
358
asked Nov 12 at 19:40
Henry Wang
358
asked Nov 12 at 19:40
Henry Wang
358
asked Nov 12 at 19:40
Henry Wang
358
358
marked as duplicate by paulsm4, Community♦ Nov 13 at 1:30
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by paulsm4, Community♦ Nov 13 at 1:30
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
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 at 19:42
"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.
– paulsm4
Nov 12 at 19:43
stackoverflow.com/questions/2467751/quicksort-vs-heapsort
– esprittn
Nov 12 at 19:46
1
@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 at 3:41
add a comment |
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 at 19:42
"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.
– paulsm4
Nov 12 at 19:43
stackoverflow.com/questions/2467751/quicksort-vs-heapsort
– esprittn
Nov 12 at 19:46
1
@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 at 3:41
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 at 19:42
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 at 19:42
"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.
– paulsm4
Nov 12 at 19:43
"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.
– paulsm4
Nov 12 at 19:43
stackoverflow.com/questions/2467751/quicksort-vs-heapsort
– esprittn
Nov 12 at 19:46
stackoverflow.com/questions/2467751/quicksort-vs-heapsort
– esprittn
Nov 12 at 19:46
1
1
@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 at 3:41
@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 at 3:41
add a comment |
2 Answers
2
active
oldest
votes
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.
answered Nov 12 at 21:07
rcgldr
15.1k31333
So in the end it depends on the system...
– Henry Wang
Nov 12 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 at 21:29
1
@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
– paulsm4
Nov 13 at 1:25
add a comment |
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.
Taken from here
answered Nov 12 at 19:47
Sand
1,083114
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 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
– Sand
Nov 12 at 19:59
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
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.
answered Nov 12 at 21:07
rcgldr
15.1k31333
So in the end it depends on the system...
– Henry Wang
Nov 12 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 at 21:29
1
@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
– paulsm4
Nov 13 at 1:25
add a comment |
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.
answered Nov 12 at 21:07
rcgldr
15.1k31333
So in the end it depends on the system...
– Henry Wang
Nov 12 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 at 21:29
1
@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
– paulsm4
Nov 13 at 1:25
add a comment |
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.
answered Nov 12 at 21:07
rcgldr
15.1k31333
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.
answered Nov 12 at 21:07
rcgldr
15.1k31333
edited Nov 12 at 21:23
answered Nov 12 at 21:07
rcgldr
15.1k31333
answered Nov 12 at 21:07
rcgldr
15.1k31333
answered Nov 12 at 21:07
rcgldr
15.1k31333
15.1k31333
So in the end it depends on the system...
– Henry Wang
Nov 12 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 at 21:29
1
@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
– paulsm4
Nov 13 at 1:25
add a comment |
So in the end it depends on the system...
– Henry Wang
Nov 12 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 at 21:29
1
@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
– paulsm4
Nov 13 at 1:25
So in the end it depends on the system...
– Henry Wang
Nov 12 at 21:10
So in the end it depends on the system...
– Henry Wang
Nov 12 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 at 21:29
@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 at 21:29
1
1
@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
– paulsm4
Nov 13 at 1:25
@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
– paulsm4
Nov 13 at 1:25
add a comment |
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.
Taken from here
answered Nov 12 at 19:47
Sand
1,083114
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 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
– Sand
Nov 12 at 19:59
add a comment |
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.
Taken from here
answered Nov 12 at 19:47
Sand
1,083114
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 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
– Sand
Nov 12 at 19:59
add a comment |
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.
Taken from here
answered Nov 12 at 19:47
Sand
1,083114
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.
Taken from here
answered Nov 12 at 19:47
Sand
1,083114
answered Nov 12 at 19:47
Sand
1,083114
answered Nov 12 at 19:47
Sand
1,083114
answered Nov 12 at 19:47
Sand
1,083114
1,083114
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 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
– Sand
Nov 12 at 19:59
add a comment |
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 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
– Sand
Nov 12 at 19:59
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 at 19:51
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 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
– Sand
Nov 12 at 19:59
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
– Sand
Nov 12 at 19:59
add a comment |
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 at 19:42
"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.
– paulsm4
Nov 12 at 19:43
stackoverflow.com/questions/2467751/quicksort-vs-heapsort
– esprittn
Nov 12 at 19:46
1
@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 at 3:41