Merge Sort vs Heap Sort
Same 220 values, same shuffle, same speed. Merge Sort finishes first and turns gold: 3,178 operations to 4,307.
The numbers
- Merge operations
- 3,178
- Heap operations
- 4,307
- Merge average
- n log n
- Heap average
- n log n
- Merge worst
- n log n
- Heap worst
- n log n
Merge Sort
Merge Sort splits the list in half, sorts both halves, then merges the two sorted halves into one. More on Merge Sort.
Heap Sort
Heap Sort builds a max-heap from the list, then repeatedly moves the largest value to the end. More on Heap Sort.
FAQ
Which is faster, Merge Sort or Heap Sort?
On this shuffle of 220 values, Merge Sort needed 3,178 operations and Heap Sort needed 4,307, about 1.4× as many. On average Merge Sort is n log n and Heap Sort is n log n.
Which one is stable?
Merge Sort is stable; Heap Sort is not.
How is the race fair?
Both algorithms start from the same shuffle and run the same number of operations per frame. Every comparison, swap and write counts as one operation, so the one that needs fewer operations finishes first.