17.1.4. Stability in Insertion Sort

So, one of the important criteria that we should not forget is that, sorting often happens in phases. So, we might have a list of names of people say Aswin, Bharathi, Chander and Deepa. So, we have sorted this in order and they might have got some marks in an exam. So, they may be got 60, 43, 60 and 95, now we might want to sort this by marks.

In sorting, especially when handling lists that have multiple attributes (like names and marks), it’s crucial to remember that sorting occurs in phases. For example, if we have a list of students and their scores, initially sorted by names, switching the sort criteria to marks must ensure that the alphabetical order is not disturbed among those with identical marks. If we have Aswin, Bharathi, Chander, and Deepa with marks 60, 43, 60, and 95 respectively, sorting solely by marks must still retain the order of Aswin and Chander, who both scored 60, in their alphabetical arrangement.

Imagine organizing books on a shelf first by genre and then by author's last name. If two authors have the same last name, you wouldn't want to change their order just because they are now being sorted by the number of books they've written. Stability in sorting is akin to ensuring that even when you change the sorting criteria, the order remains consistent for items that share common characteristics.

So, this final answer should be Bharathi has 43, Ashwin has 60, Chander has 60 and Deepa has 95. But, it would be wrong if you said Chander and then Ashwin are wrong, but undesirable.

The outcome of sorting should reflect a coherent and logical order. If we were to incorrectly manipulate the order while sorting, such as placing Chander before Ashwin after sorting by marks instead of keeping their original alphabetical order, it would result in confusion. Thus, a stable sorting algorithm maintains the relative order of those with equal sorting attributes, ensuring clarity and predictability in the results.

Think of a concert lineup. If performers are listed in alphabetical order by their names but are later grouped by popularity, the show program should still respect that order for those who share the same popularity ranking. If suddenly a lesser-known artist is presented before a well-known one just because of a change in criteria, it would lead to audience confusion.

So, quick sort as shown is not a stable operation. So, remember that we took that at a bit and in the at least in our implementation what we did was we constructed this lower set and then the upper set to the right of it.

The distinction between stable and unstable sorting algorithms is crucial. For instance, quicksort is often not stable because the process of partitioning it employs swaps that can disrupt the original order of elements with equal keys (like marks of 60 in our previous example). When items are moved across large distances in the list, their arrangement can be altered, resulting in loss of the original sorting order.

Consider a group project where tasks are assigned to team members based on their last names. If you decide to reassign tasks based on everyone’s availability while mixing them all up, two team members with the same last name could end up in different positions, potentially leading to confusion about who is responsible for what. Keeping their original ordering stable ensures that references to these tasks remain consistent.

What about merge sort? Well, merge sort would normally be stable provided… all we want that something to the right should not go to the left of something in the original array.

Merge sort tends to preserve stability. When merging two sorted subsets, the algorithm is designed to retain the original order of equal elements. For instance, if two elements being merged are equal, the one that appears first in the original list will also appear first in the merged result. This is achieved by choosing the element from the left subset first when two elements are equal.

Envision sorting athletes by their scores while maintaining their previous ranking in competitions. If two athletes scored the same, the one who ranked higher in their previous matches should still be recognized first in the output. The merge process operates like a referee ensuring fairness in updating scores without changing previous records.

You can also check that similarly, if you do insertion sort carefully, then insertion sort is also stable and this is not to say that quick sort cannot be made stable.

Insertion sort is stable when implemented correctly. Similar to merge sort, when inserting elements into the sorted region, equal elements can be placed in the existing order. This characteristic allows insertion sort to maintain the stability of sorting, provided it doesn't swap elements unnecessarily.

Imagine a line of people forming a queue. If the individuals want to hold their place when a new person is added to the line, no one will be pushed ahead of someone with the same standing (like 'favorite color'). This orderly process keeps everyone in their original sequence while accommodating newcomers.

--