1
00:00:00,720 --> 00:00:03,120
Hi everyone, let's do this question.

2
00:00:03,120 --> 00:00:05,370
You are given an array of integers.

3
00:00:05,370 --> 00:00:11,910
Write a function that will take this array as input and return the sorted array using merge sort.

4
00:00:11,910 --> 00:00:16,410
So we are asked to sort a given array of integers using merge sort.

5
00:00:16,410 --> 00:00:22,110
So if this is the given array, then we have to sort it and the output would be 12357.

6
00:00:22,110 --> 00:00:25,680
And we have to do this using merge sort which is a very famous sort.

7
00:00:25,710 --> 00:00:29,760
Now let's go ahead and discuss merge sort in depth in this video.

8
00:00:29,760 --> 00:00:33,900
Now merge sort is a divide and conquer algorithm.

9
00:00:33,900 --> 00:00:40,680
With this we mean that we divide the given problem into subproblems and then we solve the subproblems,

10
00:00:40,680 --> 00:00:43,260
which in turn helps us to solve the given problem.

11
00:00:43,260 --> 00:00:45,930
So that's how a divide and conquer algorithm works.

12
00:00:45,930 --> 00:00:52,140
Now with respect to merge sort, the divide part is that we keep dividing the given array till it is

13
00:00:52,140 --> 00:00:57,930
of size one, and we use the property that an array of size one is already sorted.

14
00:00:57,930 --> 00:00:58,290
Right.

15
00:00:58,290 --> 00:00:59,670
Because you just have one element.

16
00:00:59,670 --> 00:01:01,230
So it's it has to be sorted.

17
00:01:01,230 --> 00:01:06,540
So for example if you have an array and it has just one element let's say five, this array over here

18
00:01:06,540 --> 00:01:07,620
is already sorted.

19
00:01:07,620 --> 00:01:10,410
So this property is used by merge sort.

20
00:01:10,440 --> 00:01:10,860
All right.

21
00:01:10,860 --> 00:01:16,050
And when it comes to the concre part we merge the sorted arrays.

22
00:01:16,050 --> 00:01:16,470
Right.

23
00:01:16,470 --> 00:01:19,740
So over here we have the array sorted and we merge them.

24
00:01:19,740 --> 00:01:21,300
We merge the sorted arrays.

25
00:01:21,720 --> 00:01:24,840
So we have let's say we have two arrays of size one.

26
00:01:24,840 --> 00:01:26,970
Let's say we have five and four.

27
00:01:26,970 --> 00:01:32,340
Now we merge them and we get four comma five because we merge the sorted arrays.

28
00:01:32,340 --> 00:01:36,060
And this keeps happening even when the size is no longer one.

29
00:01:36,060 --> 00:01:38,100
Now over here for example, the size is two.

30
00:01:38,100 --> 00:01:40,890
And let's say we have another array with two size.

31
00:01:40,890 --> 00:01:44,730
Now this these two will be sorted already and then we merge them up.

32
00:01:44,730 --> 00:01:47,040
So that's the concre part of the merge sort.

33
00:01:47,040 --> 00:01:49,980
So merge sort is a divide and conquer algorithm.

34
00:01:49,980 --> 00:01:56,250
And we do decomposition or we divide the array and then we sort the array upwards.

35
00:01:56,250 --> 00:02:05,130
Now we will also look at in this video the complexity analysis of an algorithm to merge two sorted arrays.

36
00:02:05,130 --> 00:02:07,560
Because we will be using that in merge sort.

37
00:02:07,560 --> 00:02:14,130
And finally at the end of this section we will discuss that merge sort is a stable sort algorithm.

38
00:02:14,130 --> 00:02:15,780
We will discuss the meaning of this.

39
00:02:15,780 --> 00:02:20,250
We will discuss what is a stable sort algorithm and what is not a stable sort algorithm.

40
00:02:20,250 --> 00:02:20,790
All right.

41
00:02:20,790 --> 00:02:22,110
So let's get started.

42
00:02:22,110 --> 00:02:29,010
And first we will look at the algorithm to merge two sorted arrays because we will use this in the merge

43
00:02:29,010 --> 00:02:29,370
sort.

44
00:02:29,820 --> 00:02:30,180
All right.

45
00:02:30,210 --> 00:02:33,060
Now let's try to understand the logic behind this.

46
00:02:33,060 --> 00:02:36,150
Let's say we have two sorted arrays 257.

47
00:02:36,150 --> 00:02:39,150
This is sorted and 146 this is sorted.

48
00:02:39,150 --> 00:02:45,420
Now remember when we say that we have two sorted arrays, both of them should be either ascending or

49
00:02:45,420 --> 00:02:46,980
both of them should be descending.

50
00:02:46,980 --> 00:02:49,530
It's not that one is ascending and one is descending.

51
00:02:49,530 --> 00:02:55,290
Now in this case, let's take the case where both of them are ascending and we want to merge them.

52
00:02:55,290 --> 00:02:58,410
And the merged array should also be ascending.

53
00:02:58,410 --> 00:02:59,610
So what do we do.

54
00:02:59,610 --> 00:03:01,530
Let's have two pointers.

55
00:03:01,530 --> 00:03:01,950
All right.

56
00:03:01,950 --> 00:03:05,850
So two pointers will point at the beginning of these two arrays.

57
00:03:05,850 --> 00:03:10,650
Now we will compare these two and which is smaller among two and one.

58
00:03:10,650 --> 00:03:12,360
We can see that one is smaller.

59
00:03:12,360 --> 00:03:16,230
So let's fill that as the first element of the result array.

60
00:03:16,740 --> 00:03:17,010
All right.

61
00:03:17,010 --> 00:03:18,240
So this is the result array.

62
00:03:18,240 --> 00:03:21,660
So the smaller among these has to be the smallest right.

63
00:03:21,660 --> 00:03:24,540
Because this is the smallest among all of these.

64
00:03:24,540 --> 00:03:25,080
Right.

65
00:03:25,080 --> 00:03:27,360
And this is the smallest among all of these.

66
00:03:27,360 --> 00:03:31,740
So the smaller among these two has to be the smallest among all the elements.

67
00:03:31,740 --> 00:03:32,100
Right.

68
00:03:32,100 --> 00:03:35,910
So by just comparing two and one we see that one is the smallest.

69
00:03:35,910 --> 00:03:37,050
And we fill it over here.

70
00:03:37,050 --> 00:03:39,000
Now we have used up this one over here.

71
00:03:39,000 --> 00:03:40,920
So let's move the pointer ahead.

72
00:03:41,730 --> 00:03:42,150
All right.

73
00:03:42,180 --> 00:03:47,130
Now let's compare the elements at the pointers which is two and four.

74
00:03:47,130 --> 00:03:48,750
So we're going to compare these two.

75
00:03:48,750 --> 00:03:50,460
Let me just clear this up.

76
00:03:50,550 --> 00:03:53,880
Now we are just going to compare two and four.

77
00:03:53,880 --> 00:03:54,210
Right.

78
00:03:54,210 --> 00:03:56,460
So which among these two is the smallest.

79
00:03:56,460 --> 00:03:57,900
The smallest is two right.

80
00:03:57,900 --> 00:04:00,720
So we fill that over here and we have used up two.

81
00:04:00,750 --> 00:04:02,280
So we move the pointer ahead.

82
00:04:02,280 --> 00:04:04,320
And we keep doing this again and again.

83
00:04:04,320 --> 00:04:06,930
Right now we compare five and four.

84
00:04:06,930 --> 00:04:09,300
And the smallest among these two is four.

85
00:04:09,300 --> 00:04:11,970
So we fill four and we move the pointer ahead.

86
00:04:11,970 --> 00:04:13,920
And we compare five and six.

87
00:04:13,920 --> 00:04:15,840
The smallest among these two is five.

88
00:04:15,840 --> 00:04:18,540
So we fill that and we move the pointer over here.

89
00:04:18,540 --> 00:04:20,460
Now we compare seven and six.

90
00:04:20,460 --> 00:04:22,230
The smallest among these two is six.

91
00:04:22,230 --> 00:04:23,430
So we fill that over here.

92
00:04:23,430 --> 00:04:26,580
And then we are just left with seven which we fill over here.

93
00:04:26,580 --> 00:04:29,220
And we get the merged array.

94
00:04:29,220 --> 00:04:31,620
And this array is also sorted.

95
00:04:31,620 --> 00:04:40,200
Now we can see that the time complexity of an algorithm to merge two sorted arrays is t of is is O order

96
00:04:40,200 --> 00:04:45,180
of n plus m, where n is the size of one array and m is the size of the other array.

97
00:04:45,180 --> 00:04:45,900
Why is that?

98
00:04:45,900 --> 00:04:49,440
So we can see that we have to visit each item once right.

99
00:04:49,440 --> 00:04:51,840
So that's n plus m operations.

100
00:04:51,840 --> 00:04:59,010
So the time complexity of this algorithm that is to merge two sorted arrays is order of n plus m.

101
00:04:59,010 --> 00:04:59,820
All right.

102
00:05:00,390 --> 00:05:02,220
What about the space complexity.

103
00:05:02,220 --> 00:05:04,770
We can see that we made a new array over here right.

104
00:05:04,770 --> 00:05:05,730
This is a new array.

105
00:05:05,730 --> 00:05:09,150
And the size of this array is n plus m right.

106
00:05:09,150 --> 00:05:12,810
Where n is the size of one array and m is the size of the other array.

107
00:05:12,810 --> 00:05:18,240
So we can say that the space complexity of this algorithm is also O of n plus m.

108
00:05:18,240 --> 00:05:18,810
All right.

109
00:05:18,810 --> 00:05:19,920
So that's done.

110
00:05:19,920 --> 00:05:24,180
So we have looked at the algorithm to merge two sorted arrays.

111
00:05:24,180 --> 00:05:29,580
And we have looked at the time complexity and space complexity of this type of an algorithm.

112
00:05:30,060 --> 00:05:34,470
Now in this case the size of these two arrays was the same.

113
00:05:34,470 --> 00:05:40,200
So let's also quickly look at the case like what should have been done if it was not the same.

114
00:05:40,200 --> 00:05:44,850
Like for example, if there were extra elements over here, like let's say we have eight and nine also

115
00:05:44,850 --> 00:05:45,450
over here.

116
00:05:45,450 --> 00:05:49,470
So we are trying to sort we are trying to merge these two sorted arrays.

117
00:05:49,470 --> 00:05:49,860
Right.

118
00:05:49,860 --> 00:05:51,030
So this is also sorted.

119
00:05:51,030 --> 00:05:52,140
This is also sorted.

120
00:05:52,140 --> 00:05:55,230
Now we would have proceed as we discussed over here.

121
00:05:55,230 --> 00:06:01,830
And we will reach this stage right where the pointers at this point are over here and over here.

122
00:06:01,830 --> 00:06:03,420
And these elements are sorted.

123
00:06:03,420 --> 00:06:06,390
Now we see that we are left with these elements over here.

124
00:06:06,390 --> 00:06:09,330
And we just pick them and put them at the end over here.

125
00:06:09,330 --> 00:06:10,260
Why is that so.

126
00:06:10,260 --> 00:06:15,330
Because we know that this is the the greatest element at the current moment in the new array.

127
00:06:15,330 --> 00:06:15,780
Right.

128
00:06:15,780 --> 00:06:20,520
And these are anyway greater than these because this array over here is also sorted.

129
00:06:20,520 --> 00:06:22,680
So we just pick them and put them.

130
00:06:22,680 --> 00:06:25,530
And at the end over here and we have our result.

131
00:06:25,530 --> 00:06:26,160
All right.

132
00:06:26,160 --> 00:06:31,590
So we have seen that to merge two sorted arrays, we have seen the logic of how we can go about it.

133
00:06:31,590 --> 00:06:36,930
And we have seen that that algorithm is of order n plus m space and time.

134
00:06:36,930 --> 00:06:39,060
Now let's proceed with the merge sort.

135
00:06:40,090 --> 00:06:40,510
All right.

136
00:06:40,510 --> 00:06:42,940
Now for this, let's take an example.

137
00:06:42,940 --> 00:06:45,580
Let's say we have to sort this array.

138
00:06:45,580 --> 00:06:46,960
This is the input array.

139
00:06:46,960 --> 00:06:52,360
And let me write the indices over here 012345 and six.

140
00:06:52,360 --> 00:06:52,930
All right.

141
00:06:52,960 --> 00:06:57,520
Now what we will do is we will break this array into two halves.

142
00:06:57,520 --> 00:06:58,060
All right.

143
00:06:58,060 --> 00:07:00,520
So let's break it into two halves.

144
00:07:00,610 --> 00:07:03,190
And we have two sub arrays.

145
00:07:03,190 --> 00:07:03,700
Right.

146
00:07:03,700 --> 00:07:05,440
So let's call this the left side.

147
00:07:05,440 --> 00:07:06,640
And this is the right side.

148
00:07:06,640 --> 00:07:13,720
Now what we will do is we will again call the merge sort function on this left part right.

149
00:07:13,720 --> 00:07:15,310
So let's break this down.

150
00:07:15,310 --> 00:07:18,760
So this becomes seven three and eight five.

151
00:07:18,760 --> 00:07:20,440
So this is broken into two.

152
00:07:20,470 --> 00:07:27,310
Again we divide this 173 into two sub arrays of one length one right size one.

153
00:07:27,310 --> 00:07:33,190
So basically we are keeping on dividing till we reach arrays of size one.

154
00:07:33,190 --> 00:07:37,540
And we know that an array of size one is already sorted.

155
00:07:37,540 --> 00:07:39,250
So we are using this property.

156
00:07:39,250 --> 00:07:41,560
So an array of size one is already sorted.

157
00:07:41,560 --> 00:07:49,420
So by dividing the given array again and again till we reach an array of size one we have achieved two

158
00:07:49,420 --> 00:07:50,230
sorted arrays.

159
00:07:50,260 --> 00:07:52,600
Now these two arrays are sorted right.

160
00:07:52,600 --> 00:07:54,190
So these two are sorted.

161
00:07:54,190 --> 00:07:59,950
Now we will use the function that we discussed previously which can merge two sorted arrays.

162
00:07:59,950 --> 00:08:00,250
Right.

163
00:08:00,250 --> 00:08:03,730
So we will use that function to merge these two together.

164
00:08:03,730 --> 00:08:04,330
All right.

165
00:08:04,810 --> 00:08:05,830
So let's see that.

166
00:08:05,830 --> 00:08:09,370
So we have these two arrays which are of size one.

167
00:08:09,370 --> 00:08:10,360
And they are sorted.

168
00:08:10,360 --> 00:08:13,060
So we call our function which we discussed before.

169
00:08:13,060 --> 00:08:16,210
And this is now merged into this array over here.

170
00:08:16,210 --> 00:08:16,690
Right.

171
00:08:16,690 --> 00:08:17,860
So three comma seven.

172
00:08:17,860 --> 00:08:22,300
So let's replace that and let's replace this with three comma seven.

173
00:08:22,300 --> 00:08:22,780
All right.

174
00:08:22,780 --> 00:08:25,510
Now what we do is we we got this back right.

175
00:08:25,510 --> 00:08:30,430
We we went further and it was broken into arrays of size one.

176
00:08:30,430 --> 00:08:32,380
And then it was merged and we got it back.

177
00:08:32,380 --> 00:08:32,680
Right.

178
00:08:32,680 --> 00:08:36,640
So we came back over here after this it will process the right side.

179
00:08:36,640 --> 00:08:36,880
Right.

180
00:08:36,880 --> 00:08:39,130
The the function will process the right side.

181
00:08:39,130 --> 00:08:44,500
So what we are doing is we are recursively calling the merge sort function first on the left side then

182
00:08:44,500 --> 00:08:45,160
on the right side.

183
00:08:45,160 --> 00:08:50,320
So because we got the return from the left side, now we call it on the right side.

184
00:08:50,320 --> 00:08:53,830
So this is also broken into two arrays of size one.

185
00:08:53,830 --> 00:08:58,510
So again these two are now sorted because array of size one is sorted.

186
00:08:58,510 --> 00:09:00,310
Now we call our merge function.

187
00:09:00,310 --> 00:09:02,260
And we merge these two together right.

188
00:09:02,260 --> 00:09:03,910
So we get five comma eight.

189
00:09:03,910 --> 00:09:06,790
So let's replace this with five comma eight.

190
00:09:06,790 --> 00:09:09,220
So these two are now sorted right.

191
00:09:09,220 --> 00:09:10,510
So these two came back.

192
00:09:10,510 --> 00:09:14,800
So this will now sort and we change this one over here.

193
00:09:14,800 --> 00:09:15,040
Right.

194
00:09:15,040 --> 00:09:19,570
So we call our sort function our merge function to merge these two together.

195
00:09:19,570 --> 00:09:23,680
So merge them and we get three comma five comma seven comma eight.

196
00:09:23,680 --> 00:09:26,020
And we have already discussed how that is done before.

197
00:09:26,020 --> 00:09:26,410
Right.

198
00:09:26,410 --> 00:09:28,060
So let's replace that over here.

199
00:09:28,060 --> 00:09:29,920
And we get this array over here.

200
00:09:29,920 --> 00:09:33,640
Now because it's done for the left side it is done right.

201
00:09:33,640 --> 00:09:35,260
So it moves to the right side.

202
00:09:35,260 --> 00:09:37,480
So notice first it does the left.

203
00:09:37,480 --> 00:09:39,730
Now again you can also do first right.

204
00:09:39,730 --> 00:09:42,370
But let's say we either one has to do first right.

205
00:09:42,370 --> 00:09:44,320
So let's say we are doing left first.

206
00:09:44,320 --> 00:09:48,550
So it will keep doing left till that is done till it returns from there.

207
00:09:48,550 --> 00:09:49,660
Then it will do right.

208
00:09:49,660 --> 00:09:50,950
So this is done now.

209
00:09:50,950 --> 00:09:54,130
So now it will start processing the right side over here.

210
00:09:54,130 --> 00:09:55,960
It will break this into two arrays.

211
00:09:56,650 --> 00:09:57,250
All right.

212
00:09:57,250 --> 00:09:59,650
Now this is already of size one.

213
00:09:59,650 --> 00:10:01,810
But again let's say it's doing left first.

214
00:10:01,810 --> 00:10:05,410
So it will break this again further down to one and nine.

215
00:10:05,410 --> 00:10:07,840
So these are two arrays of size one.

216
00:10:07,840 --> 00:10:09,610
And these two are sorted already.

217
00:10:09,610 --> 00:10:09,910
Right.

218
00:10:09,910 --> 00:10:13,390
So we will call our function to merge two sorted arrays.

219
00:10:13,390 --> 00:10:15,550
And we will get one comma nine.

220
00:10:15,550 --> 00:10:18,550
So let's replace this with what we get over here.

221
00:10:18,550 --> 00:10:20,560
And we have one comma nine and five.

222
00:10:20,560 --> 00:10:20,950
Right.

223
00:10:20,950 --> 00:10:22,990
And then this is already of size one.

224
00:10:22,990 --> 00:10:24,850
So this is already sorted.

225
00:10:24,850 --> 00:10:30,220
Now we merge these two together and we get one comma five comma nine.

226
00:10:30,220 --> 00:10:33,220
And we replace this with what we got over here.

227
00:10:33,220 --> 00:10:35,170
So these two are now sorted.

228
00:10:35,170 --> 00:10:38,800
Now we call the function again to merge two sorted arrays.

229
00:10:38,800 --> 00:10:39,790
And these are merged.

230
00:10:39,790 --> 00:10:41,830
And we have our answer.

231
00:10:41,830 --> 00:10:43,000
This is now sorted.

232
00:10:43,000 --> 00:10:45,340
So this is how Merge Sort works.

233
00:10:45,340 --> 00:10:49,600
Now let's quickly take a overview of all the steps that we did.

234
00:10:49,990 --> 00:10:50,440
Right.

235
00:10:50,440 --> 00:10:51,910
We went from here to here.

236
00:10:51,910 --> 00:10:53,350
It called the left first.

237
00:10:53,350 --> 00:10:54,610
Then it went over here.

238
00:10:54,610 --> 00:10:55,690
It went over here.

239
00:10:55,690 --> 00:10:57,670
Now this was sorted right.

240
00:10:57,670 --> 00:11:03,790
So again uh, over here, I've just written it in such a manner that we can visualize all the divide

241
00:11:03,790 --> 00:11:04,300
together.

242
00:11:04,300 --> 00:11:05,740
So all of this is divide.

243
00:11:05,740 --> 00:11:09,610
And then then we had the concre part, which is the merging part.

244
00:11:09,610 --> 00:11:11,320
Again, it's not going in this order.

245
00:11:11,320 --> 00:11:12,340
We have discussed the order.

246
00:11:12,340 --> 00:11:15,640
So after this it will merge these two together.

247
00:11:15,640 --> 00:11:17,140
It will return over here right.

248
00:11:17,140 --> 00:11:18,700
Then it will process this.

249
00:11:18,730 --> 00:11:20,140
It will merge them.

250
00:11:20,140 --> 00:11:23,530
This will be returned and then this right.

251
00:11:23,530 --> 00:11:24,670
We have these two together.

252
00:11:24,670 --> 00:11:25,570
We have these sorted.

253
00:11:25,570 --> 00:11:26,980
So then it will sort this.

254
00:11:26,980 --> 00:11:28,540
So and the left part will be done.

255
00:11:28,540 --> 00:11:30,850
Similarly it will process the right part.

256
00:11:30,850 --> 00:11:34,330
So we have this is the process by which the merge sort functions.

257
00:11:34,690 --> 00:11:35,140
All right.

258
00:11:35,140 --> 00:11:39,100
Now let's look at the complexity analysis of the merge sort.