Question

Problem 3 . 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

1) Insertion sort : It is a stable sorting algorithm. It ensures that an element a[j] comes to the left of a[i] only when a[j] < a[i].

2) Shellsort : It is not a stable sorting algorithm as it doesn't maintain the relative order of any two equal entries in an array.

3) Heapsort : It is not a stable sorting algorithm because the heapify operations can change the relative order of two equal entries in an array.

4) Mergesort : It is a stable sorting algorithm. Just like selection sort, it ensures that an element a[j] comes to the left of a[i] only when a[j] < a[i].

Hope this resolves your doubt.

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