Quick Sort vs Heap Sort vs Merge Sort

Quick Sort is faster on average (O(n log n)) thanks to cache-friendly partitioning, but its worst case is O(n²). Heap Sort is slower on average due to scattered memory access, but guarantees O(n log n) on every input. Both use roughly O(1)-O(log n) extra space and neither is stable.

Choose Quick Sort for general-purpose speed where average performance matters most. Choose Heap Sort when you need a hard worst-case guarantee — real-time systems, security-sensitive code, or anywhere an adversary might craft inputs to trigger Quick Sort's O(n²) blow-up.

You do not always have to choose. Introsort runs Quick Sort but falls back to Heap Sort when recursion gets too deep, capturing Quick Sort's speed and Heap Sort's guarantee. This hybrid is what C++ std::sort uses.

Quick Sort aside, the other two members of the O(n log n) family make an interesting pair, because they agree on their time guarantee and disagree on almost everything else.

The exchange is stark: Heap Sort gives you the same worst-case guarantee as Merge Sort for no extra memory at all, and charges you stability plus cache performance for it.

Heap Sort's cache problem is worth understanding, because it explains why an algorithm with such attractive theoretical properties is rarely the default. Sifting a value down a binary heap jumps from index i to 2i+1, then to 4i+3, and so on. Those addresses are far apart, so each step tends to miss the cache. Merge Sort walks two runs sequentially, which is exactly the pattern CPUs prefetch well. In wall-clock terms Merge Sort usually beats Heap Sort despite doing more memory traffic on paper.

Choose Quick Sort when you are sorting primitives, want the best average-case speed, and can accept instability. Use a randomised or median-of-three pivot. This is the right default for numeric arrays.

Choose Merge Sort when stability matters — sorting records by one field after another — or when you need a hard O(n log n) guarantee and can afford O(n) extra memory. It is also the natural choice for linked lists, where it needs no extra space at all, and for data too large to fit in memory.

Choose Heap Sort when memory is genuinely tight and you still cannot tolerate a quadratic worst case. Embedded systems and kernel code pick it for exactly this reason. It is also the safety net inside introsort: C++'s std::sort runs Quick Sort but switches to Heap Sort if recursion gets too deep, which is how it advertises O(n log n) worst case while keeping Quick Sort's speed.

Run all three on the same shuffled array in the visualiser and watch the swap counters rather than the clock. Heap Sort's restructuring, Merge Sort's steady merging and Quick Sort's partitioning produce three completely different signatures of work.