1
00:00:00,560 --> 00:00:01,640
Welcome back.

2
00:00:01,640 --> 00:00:05,000
So far we have discussed how the merge sort functions.

3
00:00:05,030 --> 00:00:09,770
Now in this video let's look at the complexity analysis of the merge sort.

4
00:00:09,800 --> 00:00:13,580
Now the time complexity of the merge sort is O of n log n.

5
00:00:13,580 --> 00:00:17,090
And the space complexity of the merge sort is O of n.

6
00:00:17,090 --> 00:00:19,730
Let's try to think through how we get this.

7
00:00:19,760 --> 00:00:21,710
Now what does the merge sort do.

8
00:00:21,740 --> 00:00:24,500
Let's say we are given an array of length n.

9
00:00:24,530 --> 00:00:29,180
Now the merge sort will split it into two arrays of size n by two and n by two.

10
00:00:29,180 --> 00:00:34,400
And again this array would be split into two arrays of size n by four and n by four.

11
00:00:34,400 --> 00:00:38,960
And this keeps happening till we get an array of size one right.

12
00:00:38,960 --> 00:00:40,220
And then we merge back.

13
00:00:40,220 --> 00:00:41,480
So that's what we discussed.

14
00:00:41,480 --> 00:00:45,290
Right now if you take any level for example you take this level.

15
00:00:45,290 --> 00:00:48,260
You can see that we are merging n elements.

16
00:00:48,260 --> 00:00:48,650
Right.

17
00:00:48,650 --> 00:00:57,020
So we have seen that the algorithm where we merge two sorted arrays like merge two sorted arrays.

18
00:00:57,110 --> 00:01:01,160
The time complexity for that algorithm was O of n plus m.

19
00:01:01,160 --> 00:01:02,330
We have seen that right.

20
00:01:02,330 --> 00:01:06,110
So for example in this level you have when we merge them.

21
00:01:06,110 --> 00:01:06,320
Right.

22
00:01:06,320 --> 00:01:09,620
When we merge them over here we have an array of size n by four.

23
00:01:09,620 --> 00:01:12,110
And over here we have an array of size n by four.

24
00:01:12,110 --> 00:01:16,790
So in this case n by two comparisons or operations will be needed here.

25
00:01:16,790 --> 00:01:18,650
Also n by two operations will be needed.

26
00:01:18,650 --> 00:01:23,450
So in each level that's a total of n operations because we have n elements.

27
00:01:23,450 --> 00:01:29,240
You can see that right n by four plus n by four plus n by four plus n by four is a total of n elements.

28
00:01:29,240 --> 00:01:32,630
So in each level n elements are merged.

29
00:01:32,630 --> 00:01:34,190
The same is true for this level.

30
00:01:34,190 --> 00:01:36,320
Also right n by two and n by two.

31
00:01:36,350 --> 00:01:42,110
When we merge them o of n plus m is o of n by two plus n by two, which is again o of n, right.

32
00:01:42,110 --> 00:01:46,100
So in each level there are n elements that are being merged.

33
00:01:46,100 --> 00:01:46,700
Right.

34
00:01:47,090 --> 00:01:51,170
And again all these elements are part of sorted arrays in each particular level.

35
00:01:51,170 --> 00:01:56,240
So we can say that in each level we have to visit n elements and merge them.

36
00:01:56,240 --> 00:02:03,680
So the time complexity is nothing but the total number of operations which will be equal to O of n into

37
00:02:03,680 --> 00:02:04,580
number of levels.

38
00:02:04,580 --> 00:02:05,030
Right.

39
00:02:05,030 --> 00:02:09,200
Again, let me repeat in each level we have to do we have to visit n elements.

40
00:02:09,200 --> 00:02:14,450
So the total number of visitations that have to be done is nothing but number of levels into n.

41
00:02:14,450 --> 00:02:16,610
And that will give us our time complexity.

42
00:02:16,610 --> 00:02:17,000
Right.

43
00:02:17,000 --> 00:02:21,470
So time complexity is equal to O of n into number of levels.

44
00:02:21,470 --> 00:02:23,630
Now let's make some space over here.

45
00:02:24,200 --> 00:02:28,970
We have established that the time complexity is equal to O of n into number of levels.

46
00:02:28,970 --> 00:02:33,140
Now if you consider again you could think that for dividing.

47
00:02:33,140 --> 00:02:36,470
Also, why do we only consider merging even for dividing.

48
00:02:36,470 --> 00:02:38,000
It's an O of n operation.

49
00:02:38,000 --> 00:02:44,510
So if you consider it in that manner, in each level we are again, uh, the division is happening on

50
00:02:44,510 --> 00:02:45,170
n elements.

51
00:02:45,170 --> 00:02:45,620
Right.

52
00:02:45,620 --> 00:02:50,930
So for the division also in each level there is an O of n operation.

53
00:02:50,930 --> 00:02:56,900
So if we add that that would be n plus N2N operations on each level.

54
00:02:56,900 --> 00:03:02,780
So the time complexity would be two n into number of levels O of two n into number of levels.

55
00:03:02,780 --> 00:03:05,360
And because two is a constant we can just remove it.

56
00:03:05,360 --> 00:03:05,660
Right.

57
00:03:05,660 --> 00:03:12,440
So again we get that the time complexity of the merge sort is nothing but order of n into the number

58
00:03:12,440 --> 00:03:13,430
of levels.

59
00:03:13,430 --> 00:03:13,940
All right.

60
00:03:13,940 --> 00:03:15,170
So we have established this.

61
00:03:15,170 --> 00:03:16,490
So I've written it over here.

62
00:03:16,490 --> 00:03:20,960
Now let's again look at the tree over here we have an array of size n.

63
00:03:20,960 --> 00:03:26,300
It's broken into two arrays of size n by two n by two which is again broken into n by four, n by four,

64
00:03:26,300 --> 00:03:28,790
etc. till we reach an array of size one.

65
00:03:28,790 --> 00:03:30,680
So that's what's happening right now.

66
00:03:30,680 --> 00:03:32,900
How many levels are there over here.

67
00:03:32,900 --> 00:03:35,510
That's the remaining thing to be found over here, right.

68
00:03:35,510 --> 00:03:38,660
The time complexity is O of N into number of levels.

69
00:03:38,660 --> 00:03:41,570
And all we need to now find is the number of levels.

70
00:03:41,570 --> 00:03:43,520
So let's look at the pattern over here.

71
00:03:43,520 --> 00:03:44,900
Over here this is n.

72
00:03:44,930 --> 00:03:45,950
This is n by two.

73
00:03:45,950 --> 00:03:47,360
This is n by four etc..

74
00:03:47,360 --> 00:03:48,350
And we have one over here.

75
00:03:48,350 --> 00:03:48,650
Right.

76
00:03:48,650 --> 00:03:52,940
So I can write n as n divided by two to the power zero.

77
00:03:52,940 --> 00:03:53,510
Right.

78
00:03:53,510 --> 00:03:56,420
Because two to the power zero is equal to one right.

79
00:03:56,420 --> 00:04:01,760
As a side note, if you take any number like seven to the power zero, that will be 1 or 10 to the power

80
00:04:01,760 --> 00:04:02,030
zero.

81
00:04:02,030 --> 00:04:03,110
That's one, etc..

82
00:04:03,110 --> 00:04:03,530
All right.

83
00:04:03,530 --> 00:04:04,790
So that's the side note.

84
00:04:04,790 --> 00:04:08,000
So I can write n as n divided by one.

85
00:04:08,000 --> 00:04:10,490
And one can be written as two to the power zero.

86
00:04:10,490 --> 00:04:12,200
Now why am I writing it like this.

87
00:04:12,200 --> 00:04:14,240
Because over here that's the pattern.

88
00:04:14,240 --> 00:04:18,710
Right over here you have n divided by two to the power one, which is n by two.

89
00:04:18,710 --> 00:04:22,610
Over here you have n divided by two to the power two, which is n by four.

90
00:04:22,610 --> 00:04:28,550
So every level over here is n divided by two to the power, two to the power of something.

91
00:04:28,550 --> 00:04:33,740
So I can write this one also as n divided by two to the power x.

92
00:04:33,740 --> 00:04:39,110
And this x will give me the number of levels which are there over here because this is level one.

93
00:04:39,110 --> 00:04:40,700
So over here you can see you have one.

94
00:04:40,700 --> 00:04:41,750
This is level two.

95
00:04:41,750 --> 00:04:42,740
Over here you have two.

96
00:04:42,740 --> 00:04:44,390
So this is level X.

97
00:04:44,390 --> 00:04:46,520
And I just need to find this x.

98
00:04:46,520 --> 00:04:47,660
So let's solve it.

99
00:04:47,660 --> 00:04:51,020
So n divided by two to the power x is equal to one.

100
00:04:51,020 --> 00:04:52,640
So let's take this to this side.

101
00:04:52,640 --> 00:04:55,400
So I get n is equal to two to the power x.

102
00:04:55,850 --> 00:04:59,180
Now if I take log on both sides I can get x.

103
00:04:59,560 --> 00:05:01,540
Is equal to log n right.

104
00:05:01,540 --> 00:05:03,220
So x is equal to log n.

105
00:05:03,220 --> 00:05:07,720
Again we have seen this in the video where we discussed Big-O and logarithm.

106
00:05:07,720 --> 00:05:08,200
Right.

107
00:05:08,200 --> 00:05:09,940
Again let's just repeat it over here.

108
00:05:09,940 --> 00:05:12,040
This is log n to the base two.

109
00:05:12,040 --> 00:05:12,520
Right.

110
00:05:12,520 --> 00:05:14,620
So this is x.

111
00:05:14,620 --> 00:05:18,370
And as we discussed over here this gives me the number of levels.

112
00:05:18,370 --> 00:05:23,320
So the number of levels in this case is equal to x which is equal to log n.

113
00:05:23,320 --> 00:05:26,980
And when we say log n it's always log n to the base two.

114
00:05:26,980 --> 00:05:33,580
Quick side note if you've not if you don't remember what this is let's say uh you have four.

115
00:05:33,580 --> 00:05:34,780
So log four.

116
00:05:35,650 --> 00:05:37,510
That's equal to two, right?

117
00:05:37,510 --> 00:05:44,080
So log four is nothing but asking two to the power what is equal to four.

118
00:05:44,080 --> 00:05:46,030
And we know two square is equal to four.

119
00:05:46,030 --> 00:05:47,920
So this is equal to two right.

120
00:05:47,950 --> 00:05:50,260
Now if you want to find log 16.

121
00:05:50,260 --> 00:05:52,660
So this is nothing but asking two to the power.

122
00:05:52,660 --> 00:05:55,660
What is equal to 16 right now.

123
00:05:55,660 --> 00:05:57,880
Two to the power four is equal to 16.

124
00:05:57,880 --> 00:06:01,420
So this is equal to log 16 is equal to four.

125
00:06:01,450 --> 00:06:02,770
That's a quick side note.

126
00:06:02,770 --> 00:06:03,220
All right.

127
00:06:03,220 --> 00:06:04,870
So let me just erase this.

128
00:06:04,870 --> 00:06:06,700
And we come back to where we were.

129
00:06:06,700 --> 00:06:10,420
We have seen that x in this case is equal to log n.

130
00:06:10,420 --> 00:06:16,150
And that gives us that the number of levels in this tree structure over here is equal to log n.

131
00:06:16,150 --> 00:06:19,000
And we have our time complexity right.

132
00:06:19,030 --> 00:06:22,630
Time complexity is equal to o of n into number of levels.

133
00:06:22,630 --> 00:06:23,230
Right.

134
00:06:24,120 --> 00:06:29,940
So the number of levels over here, this is level one, this is level two etc. this is level log n right.

135
00:06:29,940 --> 00:06:34,410
So we can now fill in over here number of levels as log n.

136
00:06:34,410 --> 00:06:36,090
So let's do that over here.

137
00:06:36,180 --> 00:06:40,020
So time complexity will be o of n into log n.

138
00:06:40,020 --> 00:06:42,210
And that gives us our answer.

139
00:06:42,210 --> 00:06:45,570
Again quick side note let's say we have eight elements.

140
00:06:45,570 --> 00:06:47,040
So how will it split.

141
00:06:47,070 --> 00:06:48,750
We will have four elements four elements.

142
00:06:48,750 --> 00:06:51,720
This will split into two and two and then one and one right.

143
00:06:51,720 --> 00:06:54,330
So you can see we have three elements over here.

144
00:06:54,330 --> 00:06:54,690
Right.

145
00:06:54,690 --> 00:06:58,320
And again remember log eight is nothing but three.

146
00:06:58,320 --> 00:07:01,770
So log A to the power two is 3 or 2 to the power.

147
00:07:01,770 --> 00:07:02,820
What is equal to eight.

148
00:07:02,820 --> 00:07:03,990
That's equal to three.

149
00:07:03,990 --> 00:07:07,350
Again I'm just repeating this over here because it's difficult for many students.

150
00:07:07,350 --> 00:07:11,250
So let's quickly again take the case where we have 16 elements.

151
00:07:11,250 --> 00:07:11,610
Right.

152
00:07:11,610 --> 00:07:13,230
Let's say we have 16 elements.

153
00:07:13,230 --> 00:07:15,420
So all you need to do is two to the power.

154
00:07:15,420 --> 00:07:16,830
What is equal to 16.

155
00:07:16,830 --> 00:07:19,260
We know two to the power four is equal to 16.

156
00:07:19,260 --> 00:07:23,160
So in this case log 16 is equal to four.

157
00:07:23,490 --> 00:07:26,190
So that gives us the height right.

158
00:07:26,190 --> 00:07:28,620
The depth of this tree the depth of this tree.

159
00:07:28,620 --> 00:07:29,190
All right.

160
00:07:29,190 --> 00:07:33,300
Now we know that time complexity is equal to O of n into number of levels.

161
00:07:33,300 --> 00:07:36,270
And we found that the number of levels is equal to log n.

162
00:07:36,270 --> 00:07:41,130
Therefore the time complexity of the merge sort is o of n into log n.

163
00:07:41,130 --> 00:07:41,910
All right.

164
00:07:42,570 --> 00:07:45,630
Now let's also look at the space complexity.

165
00:07:45,630 --> 00:07:51,390
And remember the time complexity is always O of n log n, whether it's the best case or the worst case

166
00:07:51,390 --> 00:07:58,300
or the average case, because in all the cases, the merge sort just keeps dividing the array into two

167
00:07:58,300 --> 00:07:58,680
halves.

168
00:07:58,680 --> 00:08:03,600
Right over here it's divided into halves, two halves again it's divided into two halves.

169
00:08:03,600 --> 00:08:05,550
And it keeps doing that again and again.

170
00:08:05,550 --> 00:08:12,270
So the time complexity is O of n log n, irrespective of whether it is the best case or the worst case

171
00:08:12,270 --> 00:08:13,890
or the average case.

172
00:08:14,700 --> 00:08:15,360
All right.

173
00:08:15,360 --> 00:08:17,640
Now, what about the space complexity?

174
00:08:17,670 --> 00:08:21,510
Now over here for this, we need to look at two things.

175
00:08:21,510 --> 00:08:21,870
Right.

176
00:08:21,870 --> 00:08:25,410
Are we using any extra space like creating any extra array, etc..

177
00:08:25,440 --> 00:08:27,150
That's one thing that we need to look at.

178
00:08:27,150 --> 00:08:33,240
And because the merge sort is a recursive algorithm, we need to look at the maximum depth of the tree

179
00:08:33,240 --> 00:08:39,960
so that we can know how many function calls will be there in the call stack at any given point of time.

180
00:08:39,960 --> 00:08:44,670
What is the maximum number of function calls that can be there in the call stack at any given point

181
00:08:44,670 --> 00:08:45,060
of time?

182
00:08:45,060 --> 00:08:49,470
So these are the two things that we need to look at when we think about the space complexity.

183
00:08:49,470 --> 00:08:51,990
Now first let's look at the call stack.

184
00:08:51,990 --> 00:08:57,630
So over here we can see that we have seen that the depth at any point the depth is equal to log n right.

185
00:08:57,630 --> 00:09:00,090
The maximum depth is equal to log n.

186
00:09:00,090 --> 00:09:06,780
That means that at any point maximum log n functions are waiting in the call stack.

187
00:09:06,780 --> 00:09:07,200
All right.

188
00:09:07,200 --> 00:09:07,980
So we have log n.

189
00:09:07,980 --> 00:09:10,140
We have identified this log n over here.

190
00:09:10,800 --> 00:09:11,370
All right.

191
00:09:11,370 --> 00:09:14,460
Now the second part are we creating any new arrays.

192
00:09:14,460 --> 00:09:15,120
Yes.

193
00:09:15,120 --> 00:09:17,640
For example let's look at this part over here.

194
00:09:17,640 --> 00:09:21,870
When we got this our sub array and this sub array sorted.

195
00:09:21,870 --> 00:09:23,760
And what did we do after that.

196
00:09:23,760 --> 00:09:26,550
We merged these two sorted arrays.

197
00:09:26,550 --> 00:09:32,550
And we created another array of size n by two right n by four plus n by four is equal to n by two.

198
00:09:32,580 --> 00:09:39,240
Again we saw that the space complexity of the algorithm to merge two sorted arrays was O of n plus m.

199
00:09:39,240 --> 00:09:42,090
So in this case n and m are n by four.

200
00:09:42,090 --> 00:09:46,440
So it's o of n by four plus n by four which is equal to o of n by two.

201
00:09:46,440 --> 00:09:51,900
Or it's another way of saying that we are creating a new array of size n by two over here.

202
00:09:51,900 --> 00:09:56,700
But after we return this up right, we no longer need it, right?

203
00:09:56,700 --> 00:10:00,840
So after we return it up, we no longer need it and that memory is freed up.

204
00:10:00,840 --> 00:10:02,310
Now, what happens over here?

205
00:10:02,310 --> 00:10:06,120
Over here we create an array of size n right.

206
00:10:06,120 --> 00:10:08,520
So that's the greatest array which we create over here.

207
00:10:08,520 --> 00:10:08,790
Right.

208
00:10:08,790 --> 00:10:11,070
And this is the final output.

209
00:10:11,070 --> 00:10:11,430
Right.

210
00:10:11,430 --> 00:10:16,140
So over here we are using space of n right.

211
00:10:16,140 --> 00:10:18,570
So let's now we got the two aspects.

212
00:10:18,570 --> 00:10:21,390
So over here we are using space of N right.

213
00:10:21,390 --> 00:10:24,870
And over here we are using this maximum space of log n.

214
00:10:24,870 --> 00:10:26,610
Again it's a constant into log n.

215
00:10:26,610 --> 00:10:30,450
And over here we can say it's a constant into n but we can remove constants.

216
00:10:30,450 --> 00:10:30,960
All right.

217
00:10:30,960 --> 00:10:33,930
So what's the space complexity of the merge sort.

218
00:10:33,930 --> 00:10:36,990
It will be log n which is this log n over here.

219
00:10:36,990 --> 00:10:38,970
Plus this n over here.

220
00:10:38,970 --> 00:10:41,070
Again we don't need to keep adding.

221
00:10:41,070 --> 00:10:41,970
This is n by two.

222
00:10:42,000 --> 00:10:46,500
This is n etc. because after we return this up we free this up right.

223
00:10:46,500 --> 00:10:47,850
This is no longer needed.

224
00:10:47,850 --> 00:10:49,110
So we free this space.

225
00:10:49,110 --> 00:10:52,860
So at the last moment we are creating the array of size n.

226
00:10:52,860 --> 00:10:54,300
So that's this n over here.

227
00:10:54,300 --> 00:10:58,590
So the space complexity of the merge sort is O of log n plus n.

228
00:10:58,590 --> 00:11:04,260
But because log n is less than n we can avoid this right n dominates.

229
00:11:04,260 --> 00:11:09,840
Therefore we can say that the space complexity of the merge sort is o of n.

230
00:11:10,810 --> 00:11:11,410
All right.

231
00:11:11,770 --> 00:11:13,540
So we have seen that.

232
00:11:13,930 --> 00:11:16,510
Let's quickly revise what all have we discussed so far.

233
00:11:16,510 --> 00:11:23,710
We have seen that for the algorithm to merge two sorted arrays, the space and time complexity is O

234
00:11:23,710 --> 00:11:29,380
of n plus m, right where n and m are the respective sizes of the two sorted arrays.

235
00:11:29,380 --> 00:11:35,590
We have seen that for the merge sort, the time complexity is O of n log n, and the space complexity

236
00:11:35,590 --> 00:11:36,550
is O of n.

237
00:11:36,550 --> 00:11:42,460
And remember, log n is nothing but the number of levels right of the of the tree.

238
00:11:42,460 --> 00:11:46,090
Right when we when merge sort keeps dividing the given array.

239
00:11:46,090 --> 00:11:48,820
So log n gives us the number of levels.

240
00:11:48,820 --> 00:11:49,540
All right.

241
00:11:49,540 --> 00:11:55,090
And we also saw that merge sort is a divide and conquer algorithm.

242
00:11:55,090 --> 00:12:02,410
And we saw that the time complexity of the merge sort is O of n log n, irrespective of whether it's

243
00:12:02,410 --> 00:12:05,350
the best case, worst case or the average case.

244
00:12:05,350 --> 00:12:10,930
And that's because it always divides the array into two halves, whether it's the best, worst, or

245
00:12:10,930 --> 00:12:11,710
average case.

246
00:12:11,710 --> 00:12:15,760
And then it takes linear time to merge those arrays.

247
00:12:15,760 --> 00:12:16,240
Right.

248
00:12:16,240 --> 00:12:21,460
So the time complexity of the merge sort is always o of n log n.

249
00:12:21,460 --> 00:12:28,780
And as the last point, let's also consider the fact that merge sort is a stable sorting algorithm.

250
00:12:28,780 --> 00:12:31,510
This is something which is very good about the merge sort.

251
00:12:31,510 --> 00:12:33,580
So let's discuss this aspect.

252
00:12:34,090 --> 00:12:34,570
Now.

253
00:12:34,570 --> 00:12:38,440
What do we mean when we say that the merge sort is a stable sorting algorithm?

254
00:12:38,440 --> 00:12:44,770
It means that when there is a tie between two elements and we are trying to sort, then the initial

255
00:12:44,770 --> 00:12:47,320
relative ordering is maintained.

256
00:12:47,320 --> 00:12:49,690
Let's try to understand what we mean with this.

257
00:12:50,260 --> 00:12:53,590
So let's again take the example through which we walked through.

258
00:12:53,590 --> 00:12:55,960
So over here you can see there are two files.

259
00:12:55,960 --> 00:12:58,270
Right now they are the same value.

260
00:12:58,270 --> 00:13:04,720
So whether I put this five or this five ahead in the final output the output is still sorted correctly.

261
00:13:04,720 --> 00:13:05,140
Right.

262
00:13:05,140 --> 00:13:09,310
But what we say over here is that merge sort is a stable sorting algorithm.

263
00:13:09,310 --> 00:13:13,060
It means that the initial relative ordering is maintained.

264
00:13:13,060 --> 00:13:18,010
So in the initial relative ordering this five came ahead of this five.

265
00:13:18,010 --> 00:13:18,340
Right.

266
00:13:18,340 --> 00:13:24,970
So over here also in the final output we will have that same order maintained.

267
00:13:24,970 --> 00:13:30,190
So that is what we mean when we say that merge sort is a stable sorting algorithm.

268
00:13:30,190 --> 00:13:32,800
And this is a great advantage of the merge sort.

269
00:13:32,800 --> 00:13:33,190
All right.

270
00:13:33,220 --> 00:13:35,590
Now let's take a quick example.

271
00:13:35,590 --> 00:13:41,140
An application of this this aspect where we say that merge sort is a stable sorting algorithm.

272
00:13:41,140 --> 00:13:46,960
Let's say we have four records over here and we have first name and year of birth.

273
00:13:46,960 --> 00:13:48,280
So these are four people.

274
00:13:48,280 --> 00:13:52,510
Now let's say initially we sort based on first name and we use merge sort.

275
00:13:52,510 --> 00:13:56,140
So we get this output over here a C D and R.

276
00:13:56,170 --> 00:13:56,530
Right.

277
00:13:56,530 --> 00:13:58,840
And then these are always together.

278
00:13:58,840 --> 00:14:00,460
So this is the satellite at this point.

279
00:14:00,460 --> 00:14:00,760
Right.

280
00:14:00,760 --> 00:14:02,080
So these all go together.

281
00:14:02,080 --> 00:14:04,720
So we have sorted this data in this manner.

282
00:14:04,720 --> 00:14:05,170
All right.

283
00:14:05,200 --> 00:14:08,770
Now let's say we are applying sort on the year of birth.

284
00:14:08,770 --> 00:14:11,920
So before we applied the sort this is the data.

285
00:14:11,920 --> 00:14:16,390
This is how it looks right now after we apply the sort on the year of birth.

286
00:14:16,390 --> 00:14:18,700
This is how the data will look like right?

287
00:14:18,700 --> 00:14:21,070
We just applied sorting on year of birth.

288
00:14:21,070 --> 00:14:25,240
So the smaller values are on top 1998 1998.

289
00:14:25,240 --> 00:14:27,190
And then we have 2002 thousand.

290
00:14:27,190 --> 00:14:33,130
Now notice that the previous arrangement is not disturbed because we used merge sort over here.

291
00:14:33,130 --> 00:14:33,520
Right.

292
00:14:33,520 --> 00:14:35,650
So for example what do I mean with that.

293
00:14:36,070 --> 00:14:39,070
Look at the relative positions of 1998.

294
00:14:39,070 --> 00:14:41,080
Previously this was the previous stage right.

295
00:14:41,080 --> 00:14:42,310
This is the previous stage.

296
00:14:42,640 --> 00:14:45,880
So over here Amal is ahead of Donna.

297
00:14:45,880 --> 00:14:46,390
Right.

298
00:14:46,390 --> 00:14:54,070
And when we called merge sort on the year of birth here still Amal is ahead of Donna.

299
00:14:54,070 --> 00:14:56,620
So the previous arrangement is not disturbed.

300
00:14:56,620 --> 00:14:57,010
Right.

301
00:14:57,010 --> 00:15:03,070
If we were only looking at this over here, even if I swapped these still year of birth is correctly

302
00:15:03,070 --> 00:15:03,670
sorted, right?

303
00:15:03,670 --> 00:15:05,980
I could have written Donna first and Amal second.

304
00:15:05,980 --> 00:15:11,380
Still, with respect to year of birth, the sorting is correct, but because merge sort is a stable

305
00:15:11,380 --> 00:15:18,010
sorting algorithm, the previous arrangement is not disturbed or the previous relative ordering is maintained

306
00:15:18,010 --> 00:15:19,060
when there is a tie.

307
00:15:19,090 --> 00:15:20,230
So over here there is a tie.

308
00:15:20,230 --> 00:15:20,680
Right.

309
00:15:20,680 --> 00:15:24,700
So this is a great application of merge sort.

310
00:15:24,700 --> 00:15:27,430
Again look at Kali and Rani over here.

311
00:15:27,430 --> 00:15:34,270
Also the 2000 of Kali comes ahead of Rani because the previous arrangement is not disturbed.

312
00:15:34,270 --> 00:15:37,780
Again, what are some other sorts which are stable?

313
00:15:37,780 --> 00:15:43,360
Insertion sort and bubble sort is also stable and for example quicksort is not stable.