Question

. A sorting algorithm is stable if the relative order of any two equal entries in the given array stays the same: when two records a[i] and a[j] are equal in content, and i < j, then the algorithm sorts the array in a way that the record originally stored in a[i], still appears to the left of the record originally stored in a[j], when the array is sorted. Which of the algorithms Insertion Sort, Shellsort, Heapsort, and Mergesort (as presented in class) are stable, which are not?

Answer 1

Based on the definition of the sorting algorithm as mentioned in the question, out of Insertion Sort, Shellsort, Heapsort and Mergesort, Insertion Sort and Mergesort are stable. They maintain stability by ensuring that a[j] comes before a[i] iff a[j] < a[i], hence when they are equal the order would be preserved.

Heapsort is not a stable algorithm because operations on heap i.e. heapify can change the relative order of the equal entries.

Shellsort is also not a stable algorithm as it may change the relative order of the equal entries.

Hope this resolves your doubt.

Please give an upvote if you liked my solution. Thank you :)