Finally, we talk about stability. This is really one of the rules of the game but it's much easier to talk about in the context of the real algorithms that we've seen so far. And really it doesn't make sense if you don't know about comparators which we just introduced. So, the typical application that I just used as an example is say the set of student records. So we have them sorted by name and this is say, something that we do just before assigning final grades. Maybe the third line there is the final grade. So it's all fine sorted by name and but then in order to distribute it out to the people leading it to the sections, what we want to do is sort by the second fields, sort by section. The problem is that when we do that, it messes up the sort by name and that's annoying. You might assume that once you have it sorted by name, then when you sorted by the second field then it should maintain the sort of by name for all that have equal keys in that second field. Actually not all sorts preserve that property that is called stability. And clearly, it's worthwhile to think about for your application whether you want or need a stable sort. And so, it's an annoying surprise for many people and many applications. So a stable sort is a sort that preserves the relative order of items with equal keys. Whichever sort are stable? That's an interesting question that we'll take a look at now. The quick bottom line is that insertion sort and mergesort are stable but not selection sort or Shellsort. And even within that bottom line, there's implementations that maybe are not stable. You have to carefully check the code to be sure. Always, in this class, we have an exercise or exam question is this version of this sort stable or not? So, students learn to recognize whether the code is stable. So this is just another typical example where we've got things sorted by time, and then what we want to do is maybe these are important events. People buying tickets to a rock concert and I'm going to sort by location what we'd hope is that it would keep the sort by time but this is a non-stable sort that doesn't do bad so then out in the location they're going to have to resort it if they use one of these. But if they use a stable sort, then it stay sorted by time and lots of applications you want stability. Alright, so let's just look at each of the algorithms that we've considered so far. Insertion Sort. Insertion Sort is stable. Why is it stable? Well, we never move equal items pass one another. In this example here, when we get A1, well that's so in this case, the index is just one that appears in the array, it's just A's and B's. When we get our second A, we stop the sort as long as we're not less. We're equal, we're not less, we stop it so we never move an equal item pass another one. If this less or less than or equal, then it wouldn't work. Or if we did the other way around and proceeded accordingly. So, equal items never move past each other in this code so therefore insertion sort is stable. But selection sort is not stable. Usually way, the way to show that a sort is not stable and it's just to see if it has a long distance exchange that might move an item pass some equal item. So, [cough] in this case, for example, for selection sort, when we do that first exchange oops, [cough] where we found the minimum A and B is in position zero. We did a long distance exchange and that catapulted that first item past any item that it might be equal putting them out of order. And that's may not get fixed so that sort is not stable. It might move items past some equal item and leave a result where items that are equal or in different order than they were originally in the file. Selection Sort is not stable. Shellsort also has long distance exchange and so it's not stable. It moves keys past other keys that could be equal and so its easy to construct examples showing that Selection Sort is not stable. And what about Mergesort? Mergesort is stable well, it's stable as long as the merge operation is stable and that operation is going to be stable depending on how we code it. And, and in our code, if the two keys are equal, it takes from the left subarray so that means that, it will always take the, if there's a two sets of equal keys, it will preserve the relative order and that's enough to show that the merge operation is stable and then therefore Mergesort is stable. Stability is an important property in sorting algorithms. Mergesort is not only efficient, it's also
