Why isn't heapsort stable?

sorting heapsort stable-sort
JMS picture JMS · Oct 12, 2013 · Viewed 41.1k times · Source

I'm trying to understand why heapsort isn't stable. I've googled this, but haven't found a good, intuitive explanation.

I understand the importance of stable sorting - it allows us to sort based on more than one key, which can be very beneficial (i.e., do multiple sortings, each based on a different key. Since every sort will preserve the relative order of elements, previous sortings can add up to give a final list of elements sorted by multiple criteria). However, why wouldn't heapsort preserve this as well?

Thanks for your help!

Answer

KD157 picture KD157 · Oct 31, 2014

Heap sort unstable example

Consider array 21 20a 20b 12 11 8 7 (already in max-heap format)

here 20a = 20b just to differentiate the order we represent them as 20a and 20b

While heapsort first 21 is removed and placed in the last index then 20a is removed and placed in last but one index and 20b in the last but two index so after heap sort the array looks like

7 8 11 12 20b 20a 21.

It does not preserve the order of elements and hence can't be stable

Related questions

Quicksort vs heapsort

Both quicksort and heapsort do in-place sorting. Which is better? What are the applications and cases in which either is preferred?

Read More
Why not use heap sort always

The Heap Sort sorting algorithm seems to have a worst case complexity of O(nlogn), and uses O(1) space for the sorting operation. This seems better than most sorting algorithms. Then, why wouldn't one use Heap Sort always as a …

Read More
How to sort an array in a single loop?

So I was going through different sorting algorithms. But almost all the sorting algorithms require 2 loops to sort the array. The time complexity of Bubble sort & Insertion sort is O(n) for Best case but is O(n^2) as …

Read More