1
00:00:00,710 --> 00:00:01,700
Welcome back.

2
00:00:01,700 --> 00:00:08,060
An interesting thing to note about the insertion sort is that the insertion sort is a stable sorting

3
00:00:08,060 --> 00:00:08,750
algorithm.

4
00:00:08,750 --> 00:00:10,280
Now what do we mean with this?

5
00:00:10,280 --> 00:00:13,220
Let's take a very simple example to understand this.

6
00:00:13,220 --> 00:00:16,730
Let's say the array which is given to us is three one and one.

7
00:00:16,730 --> 00:00:19,100
Now you can see that these two values are the same.

8
00:00:19,100 --> 00:00:20,780
So that's why I've written this in white.

9
00:00:20,780 --> 00:00:24,380
And this is written in red so that we can distinguish between these.

10
00:00:24,380 --> 00:00:26,900
Now initially I is going to point over here.

11
00:00:26,900 --> 00:00:29,660
And then we will see that they are not in the correct place.

12
00:00:29,660 --> 00:00:32,360
So we will get one comma three in this manner.

13
00:00:32,360 --> 00:00:34,610
And then I is going to point over here.

14
00:00:34,610 --> 00:00:37,280
And then we will see that these are not in the right position.

15
00:00:37,280 --> 00:00:39,140
So three would be moved over here.

16
00:00:39,140 --> 00:00:39,680
Right.

17
00:00:39,680 --> 00:00:41,540
And Jay will come over here.

18
00:00:42,290 --> 00:00:47,480
And then when we check for this, we know that this value is not greater than one.

19
00:00:47,480 --> 00:00:48,890
So we will insert one over here.

20
00:00:48,890 --> 00:00:51,560
So we will get one comma one comma three.

21
00:00:51,560 --> 00:00:52,910
So this is the final output.

22
00:00:52,910 --> 00:00:56,030
So this is how we have discussed the insertion sorting algorithm.

23
00:00:56,030 --> 00:01:01,880
Now the interesting thing to notice over here is that you can see over here the white colored one is

24
00:01:01,880 --> 00:01:04,040
coming before the red colored one.

25
00:01:04,040 --> 00:01:08,420
And you can see that the same order is preserved in the final output.

26
00:01:08,420 --> 00:01:15,050
So that is what we mean with the sorting algorithm being stable, that it means actually that if there

27
00:01:15,050 --> 00:01:22,340
is a tie between two elements, then the initial order or the initial relative ordering is maintained

28
00:01:22,340 --> 00:01:23,540
in the final output.

29
00:01:23,540 --> 00:01:26,300
So this is an interesting thing about the insertion sort.

30
00:01:26,300 --> 00:01:28,880
So the insertion sort is a stable algorithm.