## Why heapsort is unstable sort

A sort is unstable when it does not preserve the order of same valued input in the resultant output.

Unstable sort example : Input (3a , 3b) but output (3b,3a) here 3 is the value and a,b are used to denote the order of value 3.

**Now Lets see why heapsort is instable.**

When sorting (in ascending order) heapsort first peaks the largest element and put it in the last of the list. So, the element that have been picked first, stays last and the element that have been picked second stays to the second last element in the sorted list.

Again, Build-Max-Heap procedure works such that it preserve the order of same value (ex:3a,3b) in building the heap tree. For extracting the maximum element it also works from the root and try to preserve the structure of the tree (except the change for Heapify).

So, what happens, for elements with same value [3a,3b] heapsort picks 3a before 3b but puts 3a to the right of 3b. So, As the list is sorted in ascending order we get 3b before 3a in the list .

If you try heapsort with (3a,3b,3b) then you can visualize the situation.

Hope it may helped you… 🙂

Prosunjit Biswas

UTSA.

Thank for this tutorial.

Nice Information

Check out my version of Heap Sort here

http://msumca2012.blogspot.in/2013/05/heap-sort-program-in-c.html