1
00:00:00,800 --> 00:00:01,730
Hi everyone.

2
00:00:01,730 --> 00:00:04,970
In this video let's code the merge sort together.

3
00:00:04,970 --> 00:00:11,000
Now we will need a function which will take in two arrays which are sorted and which will merge those

4
00:00:11,000 --> 00:00:11,960
two sorted arrays.

5
00:00:11,960 --> 00:00:15,440
And the output array also will be a sorted array.

6
00:00:15,440 --> 00:00:18,830
So let's call that function merge sorted arrays.

7
00:00:20,530 --> 00:00:26,470
And the input for this function will be two arrays, let's call it RTÉ one and RTÉ two.

8
00:00:27,810 --> 00:00:28,200
All right.

9
00:00:28,200 --> 00:00:30,120
So this is one function that we will need.

10
00:00:30,120 --> 00:00:32,610
And then we will need the merge sort function.

11
00:00:35,310 --> 00:00:38,340
And this function also will take in an array as input.

12
00:00:38,940 --> 00:00:39,420
All right.

13
00:00:39,420 --> 00:00:40,950
So these are the two parts.

14
00:00:40,950 --> 00:00:45,840
Let's first write this part where we take in two sorted arrays and we merge them.

15
00:00:45,840 --> 00:00:47,670
And the output is also sorted.

16
00:00:47,700 --> 00:00:51,480
Now let's call the final result as the merged array.

17
00:00:53,600 --> 00:00:55,760
And let's say it's an empty array now.

18
00:00:57,310 --> 00:00:57,820
All right.

19
00:00:57,820 --> 00:00:59,800
Now we also need two pointers.

20
00:00:59,800 --> 00:01:01,060
Let's call it I and J.

21
00:01:01,060 --> 00:01:03,010
And we initialize them to zero.

22
00:01:05,950 --> 00:01:06,370
All right.

23
00:01:06,400 --> 00:01:12,790
Now, what we need to do, as we saw in the explanation video, is that we need to compare the lowest

24
00:01:12,790 --> 00:01:19,120
values of the two arrays, RTÉ one and RTÉ two, and we will find the lower value and we will put that

25
00:01:19,120 --> 00:01:22,390
into the merged array and then we will move the respective pointer.

26
00:01:22,390 --> 00:01:23,740
So that's what we are going to do.

27
00:01:23,740 --> 00:01:31,510
And this should keep happening as long as the I pointer is not is is still less than the length of the

28
00:01:31,510 --> 00:01:35,650
array one, and the j pointer is still less than the length of array two, right.

29
00:01:35,650 --> 00:01:37,090
As long as there are elements.

30
00:01:37,090 --> 00:01:38,320
So let's write that.

31
00:01:38,320 --> 00:01:42,130
So while I less than array one dot length.

32
00:01:42,880 --> 00:01:45,940
And J less than.

33
00:01:47,110 --> 00:01:48,520
RA2 dot length.

34
00:01:49,300 --> 00:01:50,140
What will we do?

35
00:01:50,140 --> 00:01:51,280
We will compare, right?

36
00:01:51,280 --> 00:01:51,970
We will compare.

37
00:01:51,970 --> 00:01:55,480
So if array one of I.

38
00:01:56,340 --> 00:01:57,060
Less than.

39
00:01:57,060 --> 00:01:58,080
Equal to.

40
00:01:59,360 --> 00:02:01,910
Are two of J.

41
00:02:01,910 --> 00:02:03,290
So we are comparing.

42
00:02:03,410 --> 00:02:06,320
If that is the case then we will push.

43
00:02:06,350 --> 00:02:10,070
Let's say we will push merged array dot push.

44
00:02:10,100 --> 00:02:15,740
We will push the lower value into the merged array which is array one of I in this case.

45
00:02:17,810 --> 00:02:19,610
Right now.

46
00:02:19,610 --> 00:02:23,180
If we do that, then that particular element is consumed.

47
00:02:23,180 --> 00:02:24,590
So we need to increment I.

48
00:02:24,680 --> 00:02:26,330
Now we do the same thing for J.

49
00:02:26,330 --> 00:02:28,190
So if if this is not the case.

50
00:02:28,190 --> 00:02:30,080
So we write the else part.

51
00:02:30,080 --> 00:02:32,090
So merged array dot push.

52
00:02:32,910 --> 00:02:35,310
Will be array two of J.

53
00:02:37,170 --> 00:02:38,430
Oops, I came down.

54
00:02:38,670 --> 00:02:39,900
All right, so we are here.

55
00:02:39,900 --> 00:02:43,230
And if this is the case we have to increment the j pointer.

56
00:02:43,230 --> 00:02:44,220
So J plus plus.

57
00:02:44,220 --> 00:02:48,630
Now over here it's important that you write here less than equal to right.

58
00:02:48,630 --> 00:02:49,710
So why is that.

59
00:02:49,710 --> 00:02:53,220
So if you just write less than and if the two values are equal right.

60
00:02:53,220 --> 00:02:54,810
So it would come falsy.

61
00:02:54,810 --> 00:02:59,310
And the element from array two would be put right.

62
00:02:59,310 --> 00:03:02,040
But we have seen that merge sort is a stable sort.

63
00:03:02,040 --> 00:03:06,540
So in case of a tie we need to maintain the initial relative order.

64
00:03:06,540 --> 00:03:09,120
So we need to have less than equal to over here.

65
00:03:09,120 --> 00:03:11,670
Let me quickly explain that to you over here.

66
00:03:11,670 --> 00:03:13,200
Let's say we have the two arrays.

67
00:03:13,200 --> 00:03:19,470
And let's say we have element four at a particular instance from array one and element four at a particular

68
00:03:19,470 --> 00:03:21,960
instance from the second array array two.

69
00:03:21,990 --> 00:03:29,160
Now if this was only array one of I less than array two of j, then when we are comparing four and four,

70
00:03:29,190 --> 00:03:34,080
this would be falsy and it would come over here and we would push the second one.

71
00:03:34,080 --> 00:03:38,610
We would push this ahead of this right then the relative order is not maintained.

72
00:03:38,610 --> 00:03:43,080
So it's important that you have less than equal to over here to maintain the relative order.

73
00:03:43,080 --> 00:03:46,320
Because we have seen that merge sort is a stable sort.

74
00:03:46,320 --> 00:03:47,130
All right.

75
00:03:47,520 --> 00:03:48,660
So let's proceed.

76
00:03:48,660 --> 00:03:50,190
We have written this part.

77
00:03:50,220 --> 00:03:54,210
Now all that remains is let's say we are out of this while loop.

78
00:03:54,210 --> 00:03:55,650
And there are still elements.

79
00:03:55,650 --> 00:03:58,020
There are still elements in array one.

80
00:03:58,020 --> 00:04:02,280
So let's check that while I less than array one dot length.

81
00:04:03,860 --> 00:04:08,930
If that is the case, we just need to push the elements to the merged array.

82
00:04:08,930 --> 00:04:09,110
Right?

83
00:04:09,110 --> 00:04:11,180
So merged array dot push.

84
00:04:13,500 --> 00:04:14,580
Array, one of I.

85
00:04:15,970 --> 00:04:17,500
And then we'll increment I.

86
00:04:17,530 --> 00:04:23,560
So as long as there are still elements in I, we just append them to the end of the merged array.

87
00:04:23,560 --> 00:04:26,590
And we do the same thing for the second array also.

88
00:04:26,590 --> 00:04:28,090
So only one of these will be true.

89
00:04:28,090 --> 00:04:28,390
Right.

90
00:04:28,390 --> 00:04:32,530
So while j less than array two dot length.

91
00:04:35,030 --> 00:04:38,960
And if that is the case, we just push those elements to the merged array.

92
00:04:38,990 --> 00:04:39,410
Dot.

93
00:04:39,410 --> 00:04:39,950
Push.

94
00:04:41,670 --> 00:04:45,150
Array two of j and we increment j.

95
00:04:46,740 --> 00:04:47,130
All right.

96
00:04:47,130 --> 00:04:49,170
So we are done with this function.

97
00:04:49,170 --> 00:04:52,560
And then we just need to return the result the final array.

98
00:04:52,560 --> 00:04:54,240
The result which is the merged array.

99
00:04:54,240 --> 00:04:55,230
So return.

100
00:04:57,710 --> 00:04:58,040
Merged.

101
00:04:58,040 --> 00:04:58,310
All right.

102
00:04:58,730 --> 00:04:59,240
All right.

103
00:04:59,240 --> 00:05:01,220
So this part of the function is done.

104
00:05:01,220 --> 00:05:04,280
Now let's go ahead and write the merge function.

105
00:05:04,280 --> 00:05:05,660
The merge sort function.

106
00:05:05,690 --> 00:05:08,090
Now what should the merge sort function do.

107
00:05:08,420 --> 00:05:13,190
First let's check whether the length of the array is less than or equal to one.

108
00:05:13,220 --> 00:05:14,120
So if.

109
00:05:16,300 --> 00:05:17,560
Array dot length.

110
00:05:18,190 --> 00:05:19,870
Less than equal to one.

111
00:05:20,570 --> 00:05:22,580
Then we just need to return the array.

112
00:05:25,430 --> 00:05:31,160
Again, this is important because as we have seen in the discussion, we will keep calling recursively

113
00:05:31,160 --> 00:05:35,540
the merge sort function till we reach the size of the array to be one.

114
00:05:35,540 --> 00:05:35,780
Right.

115
00:05:35,780 --> 00:05:38,870
And at that point we know that an array of size one is sorted.

116
00:05:38,870 --> 00:05:40,100
So we will return that array.

117
00:05:40,100 --> 00:05:41,660
So that would happen over here.

118
00:05:41,660 --> 00:05:45,080
If the array dot length is less than equal to one we return the array.

119
00:05:45,320 --> 00:05:45,860
All right.

120
00:05:45,890 --> 00:05:51,900
Now if this is not the case we will just keep breaking the array into two equal halves right into two

121
00:05:51,900 --> 00:05:52,280
halves.

122
00:05:52,730 --> 00:05:56,000
So for that let's find the middle index.

123
00:05:56,000 --> 00:05:59,150
So middle is equal to math dot floor.

124
00:06:00,220 --> 00:06:04,180
And we just find we just divide the length of the array by two.

125
00:06:04,210 --> 00:06:06,850
So array dot length divided by two.

126
00:06:06,880 --> 00:06:08,440
So we get the middle value.

127
00:06:08,470 --> 00:06:09,730
Now what do we do.

128
00:06:09,760 --> 00:06:14,770
We call merge sort recursively on the left side and the right side.

129
00:06:14,770 --> 00:06:17,050
So let's have two variables.

130
00:06:17,050 --> 00:06:19,000
Let's call it left side and right side.

131
00:06:19,000 --> 00:06:22,210
So left side is equal to we call merge sort recursively.

132
00:06:22,210 --> 00:06:25,930
So merge sort and we pass part of the array.

133
00:06:25,930 --> 00:06:27,070
So array dot slice.

134
00:06:27,070 --> 00:06:29,530
We use the dot slice operator over here.

135
00:06:29,530 --> 00:06:32,650
And we go from zero till middle right.

136
00:06:32,650 --> 00:06:33,970
So dot slice.

137
00:06:33,970 --> 00:06:38,230
When we do zero to middle it will go up to middle not including the middle element.

138
00:06:38,230 --> 00:06:40,930
That's how the dot slice operator functions right.

139
00:06:40,930 --> 00:06:42,550
So this is the left side.

140
00:06:42,550 --> 00:06:46,600
And then let's call the right side as again on the right side.

141
00:06:46,600 --> 00:06:48,490
Also we'll call merge sort recursively.

142
00:06:48,490 --> 00:06:49,900
So merge sort array.

143
00:06:51,440 --> 00:06:52,550
Dot slice.

144
00:06:52,550 --> 00:06:54,500
And then we just need to pass middle right.

145
00:06:54,500 --> 00:06:58,370
So if we just pass middle it will take all the values from middle till the end.

146
00:06:58,400 --> 00:07:00,290
So that's the left side and the right side.

147
00:07:00,290 --> 00:07:02,300
So this will keep happening recursively.

148
00:07:02,300 --> 00:07:06,980
So this over here left side will keep doing until we get it back right.

149
00:07:06,980 --> 00:07:10,640
Only then after we get the left side only then we will go to this line.

150
00:07:10,640 --> 00:07:14,150
So the recursive functions will be maintained in the call stack.

151
00:07:14,150 --> 00:07:14,690
All right.

152
00:07:14,690 --> 00:07:18,710
Now once we have the left side and the right side we just need to return right.

153
00:07:18,710 --> 00:07:19,790
So return.

154
00:07:20,490 --> 00:07:26,340
And we have to call the merge sorted arrays function, which we have written above, and we need to

155
00:07:26,340 --> 00:07:27,420
pass the two sides.

156
00:07:27,420 --> 00:07:28,380
So left side.

157
00:07:29,350 --> 00:07:30,460
And right side.

158
00:07:31,270 --> 00:07:32,290
And we are done.

159
00:07:32,290 --> 00:07:32,770
Right.

160
00:07:32,770 --> 00:07:34,570
So that's that's our function.

161
00:07:34,570 --> 00:07:36,400
Now let's go ahead and test this.

162
00:07:36,400 --> 00:07:39,010
Let's for example write an array.

163
00:07:39,520 --> 00:07:41,560
Let's say I take the array as.

164
00:07:43,970 --> 00:07:48,980
537819

165
00:07:48,980 --> 00:07:49,970
12.

166
00:07:50,150 --> 00:07:55,040
And let's now call the merge sort on this array.

167
00:07:55,040 --> 00:07:59,840
So merge sort and we will pass this array.

168
00:07:59,960 --> 00:08:00,470
All right.

169
00:08:00,470 --> 00:08:03,410
So let's run this and see if our code is working.

170
00:08:04,180 --> 00:08:04,510
All right.

171
00:08:04,510 --> 00:08:05,890
So I'm going to run this.

172
00:08:07,570 --> 00:08:07,930
All right.

173
00:08:07,930 --> 00:08:11,950
You can see we have one, three, five, seven, eight, nine, 12.

174
00:08:11,950 --> 00:08:17,440
So yes, our code is working and we have seen how to implement implement the merge sort.

175
00:08:17,440 --> 00:08:19,300
So remember we had two functions.

176
00:08:19,300 --> 00:08:21,820
One is the function to merge two sorted arrays.

177
00:08:21,820 --> 00:08:24,580
And the output array also is sorted.

178
00:08:24,580 --> 00:08:26,200
And then we have merge sort.

179
00:08:26,200 --> 00:08:30,790
And this keeps dividing and recursively calling the merge sort.

180
00:08:30,790 --> 00:08:33,580
So over here we identify.

181
00:08:33,610 --> 00:08:36,940
We broke the given array to left side and right side.

182
00:08:36,940 --> 00:08:40,810
Right and left side is again recursively calling merge sort.

183
00:08:40,810 --> 00:08:42,160
And it's passing.

184
00:08:42,160 --> 00:08:44,170
It's it's it's using the dot slice operator.

185
00:08:44,170 --> 00:08:48,460
So we are taking values of the array from zero till up to middle not including middle.

186
00:08:48,460 --> 00:08:52,630
And then for the right side we are taking values starting from the middle till the end.

187
00:08:52,630 --> 00:08:55,270
And then these are recursive calls on the merge sort.

188
00:08:55,270 --> 00:08:58,150
And then we call the merge sorted arrays to.

189
00:08:58,150 --> 00:09:02,740
Once we get once we get something back right in any call, when we have the left side and right side,

190
00:09:02,740 --> 00:09:05,080
we call the merge sorted arrays and we merge them.

191
00:09:05,080 --> 00:09:08,680
So this keeps happening and this is our merge sort.