Course contentsShow
← Computer Science
Lesson 607 of 2,87214. Heaps and Priority QueuesFree lesson

Heapsort vs Quicksort vs Mergesort

Comparing heapsort's guaranteed O(n log n) performance, in-place operation, and cache behavior with other comparison sorts.

Heapsort vs Quicksort vs Mergesort

What you'll learn: How heapsort's guaranteed performance and in-place nature compare to quicksort and mergesort in practical sorting scenarios.

The Performance Landscape

All three algorithms achieve O(n log n) time complexity, but their guarantees differ significantly:

  • Heapsort guarantees O(n log n) in all cases—best, average, and worst. No input order can make it degrade.
  • Quicksort averages O(n log n) but suffers O(n²) worst-case performance on poorly chosen pivots (though randomization nearly eliminates this).
  • Mergesort also guarantees O(n log n) in all cases, matching heapsort's consistency.

Space Complexity: The In-Place Advantage

Heapsort operates completely in-place with O(1) extra space—it rearranges the array directly using the heap structure.

Quicksort is also in-place (ignoring recursion stack space).

Mergesort requires O(n) auxiliary space for merging, making it memory-hungry for large datasets.

Cache Performance: Where Heapsort Struggles

Here's the catch: heapsort has poor cache locality. The parent-child index jumping during heapify operations accesses memory unpredictably, causing frequent cache misses.

Quicksort exhibits excellent cache locality—partitioning works with nearby elements sequentially.

Mergesort has good sequential access patterns during merging, though the extra array hurts cache efficiency.

Practical Implications

Think of heapsort as the "reliable but methodical" option—guaranteed performance, no extra memory, but not the fastest in practice. Quicksort is the "speed demon" with a tiny risk. Mergesort is the "stable, predictable friend" who needs more space.

For real-world systems: quicksort dominates general-purpose sorting due to cache efficiency. Heapsort shines when you absolutely need O(n log n) guarantees without extra memory. Mergesort wins when stability (preserving equal element order) matters.

Key Takeaway: Heapsort guarantees O(n log n) performance and operates in-place, but poor cache behavior often makes quicksort faster in practice despite its theoretical worst-case weakness.