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

Stable Algorithms:

Insertion Sort and Merge Sort.

Unstable Algorithms:

Shellsort and Heapsort

Explanation:

A Stable sorting algorithm is, if two objects in the list with equal values appear in the same order in sorted list as they are in the input list to be sorted. Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, etc. Other algorithms are not, like Heap Sort, Quick Sort, Shellsort etc.

Example :

• Sortable list : (9,8), (1,8), (9,7), (4,1), (2,6)
• Stable sorted list be like : (1,8), (2,6), (4,1), (9,8), (9,7) on every sorting.
• Unstable sorted list be like : (1,8), (2,6), (4,1), (9,8), (9,7) OR (1,8), (2,6), (4,1), (9,7), (9,8)