Welcome back.
An interesting thing to note about the insertion sort is that the insertion sort is a stable sorting
algorithm.
Now what do we mean with this?
Let's take a very simple example to understand this.
Let's say the array which is given to us is three one and one.
Now you can see that these two values are the same.
So that's why I've written this in white.
And this is written in red so that we can distinguish between these.
Now initially I is going to point over here.
And then we will see that they are not in the correct place.
So we will get one comma three in this manner.
And then I is going to point over here.
And then we will see that these are not in the right position.
So three would be moved over here.
Right.
And Jay will come over here.
And then when we check for this, we know that this value is not greater than one.
So we will insert one over here.
So we will get one comma one comma three.
So this is the final output.
So this is how we have discussed the insertion sorting algorithm.
Now the interesting thing to notice over here is that you can see over here the white colored one is
coming before the red colored one.
And you can see that the same order is preserved in the final output.
So that is what we mean with the sorting algorithm being stable, that it means actually that if there
is a tie between two elements, then the initial order or the initial relative ordering is maintained
in the final output.
So this is an interesting thing about the insertion sort.
So the insertion sort is a stable algorithm.