1
00:00:00,670 --> 00:00:01,810
Welcome back.

2
00:00:01,810 --> 00:00:05,500
Let's now walk through the code of the merge sort, which we have written.

3
00:00:05,500 --> 00:00:10,690
Let's say that we are calling the merge sort function on this array which is 5432.

4
00:00:10,690 --> 00:00:15,070
And these are the indices of the various elements zero, one, two and three.

5
00:00:15,100 --> 00:00:16,300
Now what happens.

6
00:00:16,300 --> 00:00:17,320
We are inside the function.

7
00:00:17,320 --> 00:00:17,890
Over here.

8
00:00:17,890 --> 00:00:22,960
We are checking whether the length of this array is less than equal to one, which is not the case.

9
00:00:22,960 --> 00:00:24,130
The length is four.

10
00:00:24,130 --> 00:00:27,040
So we come over here and we calculate middle.

11
00:00:27,040 --> 00:00:30,340
Middle is equal to math dot floor array dot length by two.

12
00:00:30,370 --> 00:00:33,250
Now over here the length of this array is equal to four.

13
00:00:33,250 --> 00:00:37,600
So we calculate middle as four divided by two which is equal to two.

14
00:00:37,630 --> 00:00:38,200
All right.

15
00:00:38,230 --> 00:00:40,540
Now we go ahead to the next line.

16
00:00:40,540 --> 00:00:43,690
And over here we call the merge sort function.

17
00:00:43,690 --> 00:00:47,140
And we pass array dot slice zero comma middle right.

18
00:00:47,140 --> 00:00:50,260
So let's write left side as LZ.

19
00:00:50,260 --> 00:00:53,320
So LZ left side is equal to merge sort.

20
00:00:53,320 --> 00:01:00,400
And then the array which is passed is five comma four because we are using dot slice and zero comma

21
00:01:00,400 --> 00:01:00,700
two.

22
00:01:00,700 --> 00:01:07,240
So it will start from the zeroth index which is this one over here up to the second index not including

23
00:01:07,240 --> 00:01:07,360
it.

24
00:01:07,360 --> 00:01:07,630
Right.

25
00:01:07,630 --> 00:01:11,980
So that's how the dot slice uh function which is over here works.

26
00:01:11,980 --> 00:01:12,310
Right.

27
00:01:12,310 --> 00:01:15,370
So five comma four is passed.

28
00:01:15,370 --> 00:01:18,460
And merge sort is recursively called at this point.

29
00:01:18,460 --> 00:01:21,580
Now again the indices over here are zero and one.

30
00:01:21,580 --> 00:01:28,090
Once we pass it right and we are again inside the merge sort function, we check whether the length

31
00:01:28,090 --> 00:01:30,850
of this array is equal to one, which is not the case.

32
00:01:30,850 --> 00:01:31,210
Right.

33
00:01:31,210 --> 00:01:33,790
So we are over here now which is not the case.

34
00:01:33,790 --> 00:01:36,520
So we come to the next line and we calculate middle.

35
00:01:36,520 --> 00:01:39,970
So middle is the is array dot length divided by two.

36
00:01:39,970 --> 00:01:41,800
Now array dot length is equal to two.

37
00:01:41,830 --> 00:01:42,790
So two by two.

38
00:01:42,820 --> 00:01:45,010
So we get middle is equal to one.

39
00:01:45,010 --> 00:01:49,780
Now in the next line we again recursively call merge sort on the left side.

40
00:01:49,780 --> 00:01:52,180
So we say left side is equal to merge sort.

41
00:01:52,180 --> 00:01:57,010
And at this time we pass only one element right because middle is equal to one.

42
00:01:57,010 --> 00:01:58,750
So we call it zero comma one.

43
00:01:58,750 --> 00:02:02,260
So from zero up to one not including one.

44
00:02:02,260 --> 00:02:03,640
So that's only one element.

45
00:02:03,640 --> 00:02:05,920
So we pass only one element.

46
00:02:05,920 --> 00:02:09,100
And at this point again we come to the merge sort function.

47
00:02:09,100 --> 00:02:09,460
Right.

48
00:02:09,460 --> 00:02:13,330
And we check that we see that array dot length is actually equal to one.

49
00:02:13,330 --> 00:02:15,130
And hence we return this array.

50
00:02:15,160 --> 00:02:18,130
So at this point the array five is returned.

51
00:02:18,640 --> 00:02:19,150
All right.

52
00:02:19,150 --> 00:02:22,390
And then we come to the next line right.

53
00:02:22,390 --> 00:02:24,280
We call the right side.

54
00:02:24,280 --> 00:02:30,010
And we only pass the element four right because middle is one at this point.

55
00:02:30,010 --> 00:02:33,370
So we we we do dot slice and we pass one.

56
00:02:33,370 --> 00:02:37,330
So from one which is this element, it will take all the elements which are there.

57
00:02:37,330 --> 00:02:39,850
And we see that it just has only one element right.

58
00:02:39,850 --> 00:02:44,410
So again we come to the merge sort and we see that the length of the array is one at this point.

59
00:02:44,410 --> 00:02:45,970
So this array is returned.

60
00:02:45,970 --> 00:02:46,450
All right.

61
00:02:46,450 --> 00:02:52,360
So we've got the left side and the right side over here when this was the array which is passed right.

62
00:02:52,360 --> 00:02:54,280
We got the left side and the right side.

63
00:02:54,280 --> 00:02:56,620
And next we call merge sorted arrays.

64
00:02:56,620 --> 00:03:01,660
And we pass these two arrays to the merge sorted arrays function which we have written over here.

65
00:03:01,660 --> 00:03:03,670
Now let me just make some space over here.

66
00:03:03,670 --> 00:03:04,570
Clean this up.

67
00:03:05,660 --> 00:03:06,110
All right.

68
00:03:06,110 --> 00:03:07,970
So we are over here at this point.

69
00:03:08,000 --> 00:03:12,050
Now we have the merged array which is initialized as an empty array.

70
00:03:12,050 --> 00:03:14,810
And we have I is equal to zero and j is equal to zero.

71
00:03:14,840 --> 00:03:18,920
Now we are in this while loop I is less than array one dot length.

72
00:03:18,920 --> 00:03:22,160
Array one dot length is one and array two dot length is one.

73
00:03:22,160 --> 00:03:26,150
Now I is zero, j is zero, so zero less than one and zero less than one.

74
00:03:26,150 --> 00:03:26,960
So this is true.

75
00:03:26,960 --> 00:03:29,120
So we come inside the while loop.

76
00:03:29,120 --> 00:03:35,780
Now we check whether our I that is five whether five is less than or equal to four which is not the

77
00:03:35,780 --> 00:03:36,200
case.

78
00:03:36,200 --> 00:03:38,300
So we come over here which is the else part.

79
00:03:38,300 --> 00:03:38,840
Right.

80
00:03:39,380 --> 00:03:42,290
So we check this and we come to the else part.

81
00:03:42,290 --> 00:03:44,840
And we fill four over here because it's not true.

82
00:03:44,840 --> 00:03:49,970
So from the else part we do merged array dot push array two of j which is four.

83
00:03:49,970 --> 00:03:52,760
So that's how four comes into the merged array.

84
00:03:52,760 --> 00:03:53,300
Right.

85
00:03:53,300 --> 00:03:58,370
And then we come out of the while loop because now we increment j.

86
00:03:58,370 --> 00:04:01,880
So j is now one and one less than one is false right.

87
00:04:01,880 --> 00:04:07,730
So we come out of the while loop and then we come over here over here we we see that there are still

88
00:04:07,730 --> 00:04:08,780
elements over here.

89
00:04:08,780 --> 00:04:11,660
It's um this is the this is array one.

90
00:04:11,660 --> 00:04:12,380
This is array two.

91
00:04:12,380 --> 00:04:14,690
So there are still elements in array.

92
00:04:15,170 --> 00:04:15,920
Uh one right.

93
00:04:15,920 --> 00:04:17,990
So this four was taken from array two.

94
00:04:18,020 --> 00:04:20,330
So there are still elements in array one right.

95
00:04:20,330 --> 00:04:24,500
So we do merged array dot push array one which is equal to five.

96
00:04:24,500 --> 00:04:25,940
So that five comes over here.

97
00:04:25,940 --> 00:04:29,720
And then we return the merged array which is four comma five.

98
00:04:29,720 --> 00:04:30,500
All right.

99
00:04:30,920 --> 00:04:35,120
So we came out of this part and the left side right.

100
00:04:35,120 --> 00:04:38,060
So this was a call of the left side just this right.

101
00:04:38,060 --> 00:04:40,430
So we went again deeper and deeper.

102
00:04:40,430 --> 00:04:43,940
And then once we got things back we are back at this point.

103
00:04:43,940 --> 00:04:47,960
And we have left side is equal to this array which is four comma five.

104
00:04:47,960 --> 00:04:50,690
Now we go ahead and call the right side right.

105
00:04:50,690 --> 00:04:52,820
So right side will be this part.

106
00:04:52,820 --> 00:04:54,470
We will give this part as input right.

107
00:04:54,470 --> 00:04:56,480
So right side is merge sort.

108
00:04:56,480 --> 00:04:59,930
And the input is three comma two at this which is this line over here.

109
00:04:59,930 --> 00:05:02,510
Now this will again call merge sort.

110
00:05:02,510 --> 00:05:02,840
Right.

111
00:05:02,840 --> 00:05:05,420
This is because we have we are recursively calling merge sort.

112
00:05:05,420 --> 00:05:09,740
At this point we are checking whether the length of this array is one which is not the case.

113
00:05:09,740 --> 00:05:10,730
This line over here.

114
00:05:10,730 --> 00:05:13,220
So we come over here we calculate middle right.

115
00:05:13,220 --> 00:05:14,960
So the length over here is two.

116
00:05:14,960 --> 00:05:16,310
So two by one is one.

117
00:05:16,310 --> 00:05:17,750
So middle is equal to one.

118
00:05:17,750 --> 00:05:20,420
And we do dot slice zero comma one.

119
00:05:20,420 --> 00:05:22,160
Again this is zero and this is one.

120
00:05:22,160 --> 00:05:25,910
So zero comma one will just give you one element right up to one not including one.

121
00:05:25,910 --> 00:05:29,300
So we get left side at this point is merge sort of three.

122
00:05:29,300 --> 00:05:33,170
And this returns three because the length of this array is equal to one.

123
00:05:33,170 --> 00:05:36,890
Then we go to right side is merge sort of two.

124
00:05:36,890 --> 00:05:37,340
Right.

125
00:05:37,340 --> 00:05:40,580
And this again returns two because the length of this array is two.

126
00:05:40,580 --> 00:05:45,620
So we come back over here and we have the left side and the right side over here.

127
00:05:45,620 --> 00:05:48,320
And we call merge sorted arrays.

128
00:05:48,320 --> 00:05:50,240
And we pass three and two to it.

129
00:05:50,240 --> 00:05:50,570
Right.

130
00:05:50,570 --> 00:05:54,650
And this again as we saw previously this merges these two arrays.

131
00:05:54,650 --> 00:05:58,130
And we get back two comma three as the output array.

132
00:05:58,130 --> 00:05:58,760
All right.

133
00:05:58,760 --> 00:06:00,890
So we have seen that when we called this.

134
00:06:00,890 --> 00:06:01,820
So we are back over here.

135
00:06:01,820 --> 00:06:04,340
We called this and we went deeper.

136
00:06:04,340 --> 00:06:06,590
And we came back when things started returning.

137
00:06:06,590 --> 00:06:07,640
And we got this.

138
00:06:07,640 --> 00:06:09,320
So left side is four comma five.

139
00:06:09,320 --> 00:06:11,120
And then we came to the right side.

140
00:06:11,120 --> 00:06:14,420
We went deeper and we came back when things started to return.

141
00:06:14,420 --> 00:06:17,480
And now at this point right side is equal to two comma three.

142
00:06:17,480 --> 00:06:20,090
Now we again call merge sorted arrays.

143
00:06:20,090 --> 00:06:22,670
And we pass these two arrays to it.

144
00:06:22,670 --> 00:06:23,150
All right.

145
00:06:23,180 --> 00:06:25,520
Now let's look at how things pan out.

146
00:06:26,220 --> 00:06:30,510
So we are over here now and these two arrays are passed to this function.

147
00:06:30,510 --> 00:06:35,400
Now merged array is initialized to be an empty array I is equal to zero, j is equal to zero.

148
00:06:35,400 --> 00:06:37,950
Now zero array dot one length.

149
00:06:37,950 --> 00:06:39,060
This is array dot one.

150
00:06:39,060 --> 00:06:41,700
The length of it is two and array dot two.

151
00:06:41,700 --> 00:06:42,570
Length is also two.

152
00:06:42,600 --> 00:06:45,240
So zero less than two and zero less than two.

153
00:06:45,270 --> 00:06:46,200
It's true right.

154
00:06:46,200 --> 00:06:47,520
So we come inside.

155
00:06:47,520 --> 00:06:54,030
Now we are going to compare array one of I which is four and array two of j which is two.

156
00:06:54,030 --> 00:06:58,500
Now which among these is lesser right is is it is four less than two.

157
00:06:58,500 --> 00:06:58,770
No.

158
00:06:58,770 --> 00:07:02,250
So we come to the else part over here, we come to the else part over here.

159
00:07:02,250 --> 00:07:04,710
And we push two to the merged array.

160
00:07:04,710 --> 00:07:07,110
So the merged array now has element two.

161
00:07:07,110 --> 00:07:08,310
And what do we do.

162
00:07:08,310 --> 00:07:09,240
We increment j.

163
00:07:09,240 --> 00:07:12,690
So j is now pointing to this pointer right.

164
00:07:12,690 --> 00:07:14,610
And still j is one.

165
00:07:14,610 --> 00:07:19,080
And this is still true because over here I is zero zero less than two and one less than two.

166
00:07:19,110 --> 00:07:19,770
It's still true.

167
00:07:19,770 --> 00:07:25,470
So again we come inside this loop and we are checking array one of I which is four.

168
00:07:25,470 --> 00:07:28,740
And array two of j which is three.

169
00:07:28,740 --> 00:07:28,980
Right.

170
00:07:28,980 --> 00:07:32,190
So again we see that four is not less than three.

171
00:07:32,190 --> 00:07:38,610
So again we come to the else part and we push array two of j which is three to the merged array.

172
00:07:38,610 --> 00:07:39,810
So we have three over here.

173
00:07:39,810 --> 00:07:43,260
Now j is equal to two right now two less than two is false.

174
00:07:43,470 --> 00:07:49,500
So we come out of this while loop and we come over here and we check whether there is, there are whether

175
00:07:49,500 --> 00:07:51,720
I is less than R1 dot length which is true.

176
00:07:51,720 --> 00:07:52,080
Right.

177
00:07:52,080 --> 00:07:54,090
I is zero which is less than two.

178
00:07:54,090 --> 00:07:54,420
Right.

179
00:07:54,420 --> 00:07:58,230
So we push array one of I which is zero.

180
00:07:58,230 --> 00:08:03,660
So four gets pushed over here and then I comes one becomes one and one is still less than two.

181
00:08:03,690 --> 00:08:05,730
So again the next element is also pushed.

182
00:08:05,730 --> 00:08:07,650
So we get four comma five over here.

183
00:08:07,650 --> 00:08:10,200
And when we come over here J is already two right.

184
00:08:10,200 --> 00:08:12,150
So two less than two is false.

185
00:08:12,150 --> 00:08:13,680
So we don't execute this part.

186
00:08:13,680 --> 00:08:15,960
And we have our merged array.

187
00:08:15,960 --> 00:08:17,160
And this is returned.

188
00:08:17,160 --> 00:08:19,230
So this is how the merge sort works.

189
00:08:19,230 --> 00:08:21,750
So we have looked at the code we have.

190
00:08:21,750 --> 00:08:24,180
We have looked at the logic behind the merge sort.

191
00:08:24,180 --> 00:08:27,750
And we have analysed the time and space complexity of the merge sort.

192
00:08:27,780 --> 00:08:30,660
We have coded it and we have walked through the code.

193
00:08:30,660 --> 00:08:33,360
So this is what you will be expected to do in the interview.