Question

A sorting algorithm is called stable if it maintains the original (input) order of the elements with equal keys (i.e., values)

give a simple example (can be as few as three elements) to show heapsort is inherently unstable

Answer 1

Heapsort is inherently unstable because it can change the relative order of duplicate elements.

An example with an array of three elements, including a duplicate key, shows how after sorting, the original order of those with equal keys may not be preserved.

Step-by-step explanation:

A sorting algorithm is called stable if it maintains the original order of elements with equal keys when it sorts them.

An example to show that heapsort is inherently unstable could involve a simple array of three elements with values that include a duplicate key, such as [(2, 'A'), (1,'B'), (2, 'C')].

After heapsort is applied, the original order of the elements with equal keys might not be preserved.

Since heapsort is based on a binary heap data structure and it does not keep track of the original ordering of the elements, it could result in a sorted array like [(1,'B'), (2, 'C'), (2, 'A')], where the relative order of 'A' and 'C' has changed despite having the same key, which demonstrates its instability.