4 Question 4 An algorithm is called stable if elements that

4. Question 4: An algorithm is called stable if elements that are of the same value do not change their order after the sorting. (a) Is Merge-sort stable? (b) Find a way to make any sorting algorithm stable (you can add additional data to every number).

Solution

A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted. Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, etc. And some sorting algorithms are not, like Heap Sort, Quick Sort, etc.

Background: a \"stable\" sorting algorithm keeps the items with the same sorting key in order. Suppose we have a list of 5-letter words:

If we sort the list by just the first letter of each word then a stable-sort would produce:

In an unstable algorithm, straw or spork may be interchanged, but in stable sort, they stay in the same relative positions (that is, since \'straw\' appears before \'spork\' in the input, it also appears before \'spork\' in the output).

We could sort the list of words using this algorithm: stable sorting by column 5, then 4, then 3, then 2, then 1. In the end, it will be correctly sorted. Convince yourself of that. (by the way, that algorithm is called radix sort)

Now to answer your question, suppose we have a list of first and last names. We are asked to sort \"by last name, then by first\". We could first stable sort by the first name, then sort by the last name. After these sorts, the list is primarily sorted by the last name. However, where last names are the same, the first names are sorted.