Why Isn’t Heapsort Stable?

1. Introduction

A sorting algorithm is stable if two records with equal keys remain in the same order in which they were in the unsorted array.

Stable sorting algorithms are crucial in many important applications, such as radix sort.

In this article, we’ll show that heapsort, a powerful sorting algorithm with time complexity, is not stable.

2. Understanding Stability

Suppose we had the following input array of tuples:

Each tuple could represent, for example, (grade, name). Now let’s see how they would be sorted on the key grade using a stable sort:

We can immediately see that and are in the same order in which they occurred in the original unsorted array, even though one might consider the order and to be more obvious in a lexicographic sense.

This is because we’re sorting only on the key grade, and key name does not enter into consideration.

3. Heapsort

Let’s quickly review the essential aspects of heapsort.

• An input, unsorted array of records of size is given.
• A max-heap is created. This is a complete binary tree with the property that each node has key the keys of its two children.
• The maximum value in the input array is at the root of the tree.

3.1. Sorting With a Heap

We now repeat the following steps times:

1. Swap the root with the last element of the array.
2. Correct the modified max-heap (of size ) so that it still follows the heap property. This is done using the procedure sift-down.

At the end of this process, the max-heap will be sorted in increasing order.

All the above steps can be executed on the original input array — a separate binary tree is not required.

4. Heapsort Is Not Stable

Let’s demonstrate, using a counterexample, that heapsorts are not stable.

We’ll use the same array of tuples that we presented above. In the following the input data is in an array with indexes :

4.1. Making a Max-Heap

We can construct a max-heap corresponding to this array, as shown below. We can satisfy ourselves that each node has a key value its children.

We can also see that the maximum element in the array sits in the root:

We can now interchange the root element (index 1) with the last element (index 7) in the array. This puts in its final and correct position, i.e. in index 7. The purple line indicates that the sub-array composed only of is correctly sorted:

4.2. Correcting the Heap Using Sift-Down

We observe that the tree no longer satisfies the max-heap property, since at index has a smaller key than its two children, which have keys 89 and 72.

We can correct this problem by a sequence of interchanges that move the maximum element in to the root and adjusts the remaining nodes appropriately. The procedure to do this is called sift-down:

The nodes form a proper max-heap, with the maximum element at the root. We can now interchange the elements at node 1 with the element at . We can see (as indicated by the purple line), that elements are properly sorted:

4.3. Continuing the Correction

The tree made up of nodes is again not a proper max-tree, so we’ll apply the correction procedure sift-down to obtain:

We can now exchange node 1 and node 5 to put in its final location in the sorted array:

4.4. Where Do We Stand Now?

We could continue this process until the entire array was sorted. However, at the moment we see that are , and , respectively.

These are the final positions of the tuples, and we notice that precedes . In the original array precedes . Thus, heapsort is not stable.

5. Conclusion

Stable sorting algorithms have many important applications. Heapsort, though it is an efficient () algorithm, is not stable, as we have demonstrated with a counterexample. To evaluate the stability of a sorting algorithm, we need to think in terms of records with a specific sorting key, as we have done with tuples. Merely thinking in terms of numbers does not give us much insight into the stability issue.