1
00:00:02,220 --> 00:00:03,030
Hi, everyone.

2
00:00:03,060 --> 00:00:09,650
So in this video, we are going to discuss another sorting algorithm, so much art, so much orders

3
00:00:09,690 --> 00:00:15,060
and the sorting algorithm, but it uses recursion so much as a recursive algorithm.

4
00:00:15,300 --> 00:00:17,700
And my thought is basically very, very fast.

5
00:00:19,160 --> 00:00:26,540
So it's a very fast sorting algorithm, so since it's a recursive algorithm, so let's discuss about

6
00:00:27,110 --> 00:00:27,870
the base case.

7
00:00:28,320 --> 00:00:29,930
So basically, it's a very simple.

8
00:00:31,940 --> 00:00:32,970
I want to show tonight.

9
00:00:33,710 --> 00:00:40,400
And if the length of the original so if the length of the zero, that means my area is empty or the

10
00:00:40,400 --> 00:00:41,570
length of the ad is one.

11
00:00:41,750 --> 00:00:48,080
So zero or one if the length of zero zero elements or one element I can say my area sorted so I will

12
00:00:48,080 --> 00:00:49,550
not do anything and I will return.

13
00:00:50,660 --> 00:00:53,420
So now let's talk about the recursive case.

14
00:00:54,620 --> 00:00:58,650
So we will be given an array and I want to sort this area.

15
00:00:58,700 --> 00:01:03,840
So I want to apply my algorithm on this area so that this area can be sorted.

16
00:01:05,510 --> 00:01:07,190
So what do we lose?

17
00:01:07,200 --> 00:01:10,700
Our first step is basically we will divide that into two parts.

18
00:01:11,690 --> 00:01:12,590
So this is start.

19
00:01:12,750 --> 00:01:13,550
This is end.

20
00:01:13,550 --> 00:01:16,880
And this is so divided into two parts.

21
00:01:16,910 --> 00:01:18,770
Let's say the name of this area is E!

22
00:01:19,850 --> 00:01:24,050
So this will be my first study and this will be my secondary.

23
00:01:24,530 --> 00:01:26,450
So we'll divide the area into half.

24
00:01:26,960 --> 00:01:30,030
OK, so divided into two parts of equal size.

25
00:01:30,950 --> 00:01:34,890
So let's say the name of this area is X and the name of Dissatisfy.

26
00:01:35,150 --> 00:01:38,810
So if the elements are five four, two, five four, two will come here.

27
00:01:39,080 --> 00:01:44,370
And if the elements here are legit, three, seven and one, two, three, seven one will come here.

28
00:01:44,930 --> 00:01:46,270
So first step is very simple.

29
00:01:47,390 --> 00:01:54,360
You will divide that into two have the second step is basically apply my thought on this area.

30
00:01:54,620 --> 00:01:56,110
I apply my thought on this area.

31
00:01:56,330 --> 00:01:57,560
So it is the property of my.

32
00:01:58,190 --> 00:02:00,500
So given an area majority will sort that.

33
00:02:00,890 --> 00:02:02,690
So this area will get sorted.

34
00:02:03,200 --> 00:02:04,470
This area will get sorted.

35
00:02:04,490 --> 00:02:06,050
So it will become two, four, five.

36
00:02:07,280 --> 00:02:08,479
So this is your area.

37
00:02:09,199 --> 00:02:11,290
And similarly, this idea will get sorted.

38
00:02:11,300 --> 00:02:13,550
So it will become one, three and seven.

39
00:02:13,910 --> 00:02:17,930
OK, we are applying my apply my chart on Adebiyi.

40
00:02:20,180 --> 00:02:22,460
And similarly, I blame my thought on that.

41
00:02:23,300 --> 00:02:27,020
What is the meaning of applying what I blame on Sarbanes called preclusion?

42
00:02:27,650 --> 00:02:29,210
So it's a recursive algorithm.

43
00:02:29,210 --> 00:02:33,080
It's recursive algorithm, so called equation decided this will get sorted.

44
00:02:33,350 --> 00:02:34,760
I will call this area.

45
00:02:34,790 --> 00:02:36,170
So this idea will get sorted.

46
00:02:37,100 --> 00:02:39,610
So after applying them, I thought after calling litigation.

47
00:02:39,860 --> 00:02:44,620
So now we have to sort it out is we have to sort it out is and what do we need to do?

48
00:02:45,230 --> 00:02:46,940
We need to merge, sort it out.

49
00:02:47,180 --> 00:02:48,280
So this is area.

50
00:02:48,650 --> 00:02:53,740
So we need to merge those already into Arrietty.

51
00:02:55,280 --> 00:03:01,480
So much to sort of that is much, much closer to that X and Y and to Arrietty.

52
00:03:02,120 --> 00:03:05,480
So if you will merge these two areas, your area will become one to.

53
00:03:06,580 --> 00:03:12,700
Then three, four, five and seven, so your array will be sorted, your area will become sorted.

54
00:03:12,740 --> 00:03:14,470
OK, so this was your original area.

55
00:03:14,770 --> 00:03:19,670
Now this area has been sorted, so I hope you understood the algorithm.

56
00:03:20,050 --> 00:03:22,210
So let me explain you that algorithm one more time.

57
00:03:22,960 --> 00:03:30,880
So the first step is basically first step is the arena to have to break into two equal parts?

58
00:03:33,340 --> 00:03:35,240
You will break that into two equal parts.

59
00:03:35,620 --> 00:03:43,690
Second step is basically called oxygen on board the half colocation or you can say apply mudguard on

60
00:03:43,690 --> 00:03:44,410
board of.

61
00:03:46,640 --> 00:03:53,690
I blame Mozart on board the half, and the third step is basically to apply Mozart on both part and

62
00:03:53,690 --> 00:03:57,080
the third step is very simple, much to sort of that is.

63
00:03:58,910 --> 00:04:01,850
So now you will manage to sort it out is.

64
00:04:03,860 --> 00:04:08,270
Simple, so let me explain them one more time, so this is your Urara.

65
00:04:10,540 --> 00:04:17,350
Let's say the name of this ad is a this is your area, what you will do, you will break that into two

66
00:04:17,350 --> 00:04:17,779
parts.

67
00:04:18,579 --> 00:04:20,709
So let's call this part as X..

68
00:04:21,519 --> 00:04:23,290
So this is my X.

69
00:04:24,760 --> 00:04:32,230
And this is my area, so these elements are present in that area.

70
00:04:33,040 --> 00:04:33,990
So now what will do?

71
00:04:34,510 --> 00:04:37,230
Apply my collocation on this area?

72
00:04:37,330 --> 00:04:39,660
I apply my collocation on this area.

73
00:04:39,970 --> 00:04:41,810
So this area is now sorted.

74
00:04:41,830 --> 00:04:44,620
This area will be sorted and this area will be sorted.

75
00:04:46,740 --> 00:04:48,270
Now we have to sort it out.

76
00:04:48,540 --> 00:04:50,970
So this is a sort of that this is a sorted out.

77
00:04:51,300 --> 00:04:55,930
So now we have to sort it out is and what we will do now, we will merge the two sides.

78
00:04:55,960 --> 00:05:01,720
That is, we will merge the two sorted areas in another area.

79
00:05:03,330 --> 00:05:11,310
So in area, we will merge the two sorted out X and Y and finally our area, it will be as area.

80
00:05:13,140 --> 00:05:15,670
So that is how the merger algorithm works.

81
00:05:15,690 --> 00:05:18,930
So this is the working of my algorithm.

82
00:05:20,470 --> 00:05:23,570
So let's take one example so that you guys can understand it better.

83
00:05:25,930 --> 00:05:34,450
So, for example, if I want to start this at 71 and five, six and two, I want to sort this area.

84
00:05:36,760 --> 00:05:38,150
So this is my area.

85
00:05:39,220 --> 00:05:42,140
Now what I will do so I will break that into two parts.

86
00:05:42,910 --> 00:05:45,400
So we need to divide this arena to half.

87
00:05:45,400 --> 00:05:48,400
So this is 71, the first part of 71.

88
00:05:48,760 --> 00:05:50,290
Second part is five six to.

89
00:05:52,470 --> 00:05:54,900
So divided into two have since elements.

90
00:05:55,830 --> 00:05:59,600
So one side, two elements and the other side only one element.

91
00:06:00,000 --> 00:06:04,860
Similarly, one side, two elements, and in the other side, only one element.

92
00:06:07,030 --> 00:06:13,640
So now the elements are even so one in one, seven and three, so this is only one element.

93
00:06:13,660 --> 00:06:14,830
And what was the best case?

94
00:06:15,190 --> 00:06:17,830
So best case, if you remember, if the element is one.

95
00:06:17,830 --> 00:06:23,110
So if the length is one, adelante is one, that means if only one element is there, then that element

96
00:06:23,110 --> 00:06:23,960
is already sorted.

97
00:06:24,310 --> 00:06:28,010
So basically, this is a sorted area because there is only one element, so do nothing.

98
00:06:28,450 --> 00:06:31,690
So here this will be five and six.

99
00:06:31,720 --> 00:06:35,430
We are breaking the array into two parts and this is only one element.

100
00:06:35,440 --> 00:06:36,180
So do nothing.

101
00:06:37,330 --> 00:06:41,570
So you have two areas, you have two areas and both that it has ordered.

102
00:06:41,590 --> 00:06:44,490
So one element sorted out, one element be sorted out.

103
00:06:44,980 --> 00:06:49,720
So you have two areas to sort of that is and the third step mother to sort it.

104
00:06:49,720 --> 00:06:52,020
That is so much to sort of daddy.

105
00:06:52,300 --> 00:06:56,140
So it will become two seven master sort it out.

106
00:06:56,410 --> 00:07:00,030
So we have one area, we have another area and board that is all sorted.

107
00:07:00,340 --> 00:07:03,640
So if you will merge them, this will be a new area.

108
00:07:03,640 --> 00:07:04,390
One three seven.

109
00:07:06,410 --> 00:07:08,770
So this is a sort that this is just after daddy.

110
00:07:09,090 --> 00:07:10,250
Now let's merge them.

111
00:07:11,150 --> 00:07:13,370
So after merging, it will be five and six.

112
00:07:15,380 --> 00:07:18,090
So this is a Saturday, this is a Saturday.

113
00:07:18,170 --> 00:07:19,340
Now let's merge them.

114
00:07:19,610 --> 00:07:22,550
So after merging, it will become two, five and six.

115
00:07:25,070 --> 00:07:26,870
So now we have a at Eddie.

116
00:07:27,840 --> 00:07:34,800
We have this hour today, let's march the truth out today, so we have finally will be one, then two,

117
00:07:35,370 --> 00:07:37,890
three, five, six and seven.

118
00:07:38,490 --> 00:07:42,090
So this will be your Saturday today and this will be your final at 8:00.

119
00:07:43,770 --> 00:07:45,140
So this was the original.

120
00:07:45,150 --> 00:07:48,510
This is the sort of that is so now the elements are started.

121
00:07:51,130 --> 00:07:54,820
OK, so I hope you understood the working, so can you write the code?

122
00:07:54,950 --> 00:07:56,480
Writing the code will be very simple.

123
00:07:56,830 --> 00:08:00,520
What we will do so I am only discussing the approach.

124
00:08:00,820 --> 00:08:02,220
You will write the code yourself.

125
00:08:03,550 --> 00:08:05,800
So there are two ways of writing the code.

126
00:08:07,180 --> 00:08:10,900
So what you can do, so let's talk about option one.

127
00:08:13,340 --> 00:08:20,720
So option one is basically this is the area which I want to sort, this is at a this is necessity starting

128
00:08:20,730 --> 00:08:21,150
next.

129
00:08:21,200 --> 00:08:22,460
This is the end index.

130
00:08:23,720 --> 00:08:25,900
So first step, break this down into two parts.

131
00:08:26,210 --> 00:08:28,510
So what you can do, you can create another area.

132
00:08:29,750 --> 00:08:32,590
Let's name it X, you can create another area.

133
00:08:33,200 --> 00:08:34,220
Let's name Midway.

134
00:08:34,700 --> 00:08:44,240
So you will copy all these elements here and that X and you will copy all these elements in it if I

135
00:08:45,920 --> 00:08:47,600
copy all the elements in Adibi.

136
00:08:51,390 --> 00:08:58,370
So now what will look, we will apply a much sought on Addicks, we will apply a chart on Adivasi.

137
00:08:58,830 --> 00:09:00,480
So now I have Addicks.

138
00:09:01,820 --> 00:09:07,070
Which is a sort of that I have anyway, which is a sort of daddy and I have Eddie.

139
00:09:08,650 --> 00:09:14,770
I have this every so now you will merge these two sort of daddies, so this is option one.

140
00:09:15,820 --> 00:09:17,920
Option two of solving the problem can be.

141
00:09:19,600 --> 00:09:23,380
So option two is basically this is the area which I want to sort.

142
00:09:26,180 --> 00:09:31,430
So first step is same, you will break the urethra, you will divide that into two parts.

143
00:09:31,910 --> 00:09:34,310
Now, I will not create another X and Y.

144
00:09:34,340 --> 00:09:37,720
What I will do, I will just apply them on this undercity.

145
00:09:39,890 --> 00:09:45,960
I will treat this small area as if it is an independent area, so I will apply my chart on this area.

146
00:09:47,160 --> 00:09:53,080
Similarly, what I will do, I will treat this small area as if it is independent area.

147
00:09:53,270 --> 00:09:55,630
So I will apply my chart on this area.

148
00:09:56,300 --> 00:09:58,270
So I'm not creating new areas.

149
00:09:58,280 --> 00:09:59,770
I am not creating new areas.

150
00:10:00,230 --> 00:10:04,750
I am just considering this area as if it is an independent area.

151
00:10:04,940 --> 00:10:07,970
So I am certain this area apply on this area.

152
00:10:08,180 --> 00:10:13,160
So now this area has been sorted, this area has been sorted and ready to do so.

153
00:10:13,160 --> 00:10:15,470
You need to merge these two sorted areas.

154
00:10:16,190 --> 00:10:18,820
You need to merge these two, sorted that into itself.

155
00:10:19,250 --> 00:10:21,690
So this is area and you need to merge.

156
00:10:21,830 --> 00:10:22,650
This is also already.

157
00:10:22,880 --> 00:10:23,750
So you will merge.

158
00:10:23,750 --> 00:10:29,030
You will write the code in such a fashion that these two areas, these two sorted areas after merging

159
00:10:29,030 --> 00:10:31,610
will become completely sorted.

160
00:10:32,270 --> 00:10:33,500
So which option is better?

161
00:10:33,710 --> 00:10:40,150
So this option, option two is better because we are not creating new areas, but both options are right.

162
00:10:40,250 --> 00:10:42,290
OK, so both options will work.

163
00:10:42,290 --> 00:10:43,730
Both are 100 percent right.

164
00:10:43,910 --> 00:10:45,430
You can use any one of them.

165
00:10:46,310 --> 00:10:47,900
So what do your code will look like?

166
00:10:49,790 --> 00:10:55,160
So I'm just writing only the functions you need to compute those function so that they will be void

167
00:10:55,160 --> 00:11:00,770
because I'm going to do the changes in the area itself because they are passed by my the name of the

168
00:11:00,770 --> 00:11:05,480
function is from my chart, so I will take it as input.

169
00:11:06,260 --> 00:11:08,180
I will take what is the starting next.

170
00:11:08,690 --> 00:11:10,070
What is the an index.

171
00:11:13,100 --> 00:11:19,310
And you will write the code, so I am writing a little biscuits, so biscuits will be left to zero to

172
00:11:19,310 --> 00:11:25,170
start rather than end means lanta zero and start to constraint means Lenthall one.

173
00:11:26,660 --> 00:11:28,610
So in that case, you do not need to do anything.

174
00:11:28,610 --> 00:11:29,330
You will return.

175
00:11:31,820 --> 00:11:35,420
So what is our best case, best guesses if Lanta zero?

176
00:11:37,240 --> 00:11:41,450
So to zero means start good and end all anyone.

177
00:11:41,470 --> 00:11:45,540
So if there is zero element or one element, so when means start a cause.

178
00:11:45,550 --> 00:11:47,850
And so this is a condition for one element.

179
00:11:47,860 --> 00:11:49,300
This is a condition for zero element.

180
00:11:49,300 --> 00:11:56,770
And our base case was if the length is zero or the length is one zero elements of an element so that

181
00:11:56,770 --> 00:11:58,500
it will be sorted, so do nothing.

182
00:11:58,720 --> 00:12:00,730
And this is handling both cases.

183
00:12:00,760 --> 00:12:03,830
OK, so both the cases will be handled with the help of this condition.

184
00:12:04,090 --> 00:12:05,440
So now you're ready.

185
00:12:06,070 --> 00:12:07,200
You are basically ready.

186
00:12:07,240 --> 00:12:09,390
What you will do now this is already.

187
00:12:10,420 --> 00:12:11,800
So let's apply option one.

188
00:12:11,980 --> 00:12:13,930
You can use option two also.

189
00:12:14,170 --> 00:12:17,400
But for making the problem easy, let's use option one.

190
00:12:18,070 --> 00:12:19,900
So we will use option one.

191
00:12:19,930 --> 00:12:24,280
So what you will do, you know, the starting next you know, the end of next.

192
00:12:25,480 --> 00:12:26,260
Can you find out?

193
00:12:27,040 --> 00:12:33,220
So after finding out the body will do, you will create another area X, you will copy these elements

194
00:12:33,520 --> 00:12:37,760
you will create and right away you will copy these elements.

195
00:12:37,990 --> 00:12:39,270
So now you have Erich's.

196
00:12:39,370 --> 00:12:43,750
You have anyway, so the starting next is S and the ending index is.

197
00:12:44,470 --> 00:12:47,770
So this will be made plus one and this will be.

198
00:12:47,770 --> 00:12:50,770
And so what you will do, you will call that.

199
00:12:50,770 --> 00:12:58,570
It goes in my chart on that X starting next start and then similarly you will call the onorevoli starting

200
00:12:58,570 --> 00:13:00,850
indexes murder plus one and index is.

201
00:13:00,860 --> 00:13:05,220
And so this will be sorted and this will be sorted.

202
00:13:05,470 --> 00:13:08,650
So now we have to sort that is and we need to merge them.

203
00:13:08,980 --> 00:13:10,270
So we need to merge to sort.

204
00:13:10,310 --> 00:13:15,190
That is so far that what we will do, I will write another function void merge.

205
00:13:15,670 --> 00:13:17,530
Let's say the name of the function is merge Adi.

206
00:13:18,670 --> 00:13:23,230
So Void Margera it is it will take X.

207
00:13:23,590 --> 00:13:32,950
I want to merge X and ATV into Arrietty and I will take what is this starting index and what is the

208
00:13:32,950 --> 00:13:33,640
end index.

209
00:13:36,830 --> 00:13:40,490
And they need to write the function to complete this function.

210
00:13:41,570 --> 00:13:47,690
OK, so you have an X which is sorted after applying dedication, after applying dedication.

211
00:13:47,990 --> 00:13:51,080
This is also this is this will also get sorted.

212
00:13:51,350 --> 00:13:56,930
And now what you need to do, you will call this function, Marjorie, you will pass at X, you will

213
00:13:56,930 --> 00:14:03,410
pass Ariva Buyside X, but anyway, you will pass this area, it will pass the array, it will pass

214
00:14:03,410 --> 00:14:04,980
this starting next and the next.

215
00:14:05,000 --> 00:14:06,020
This is the starting next.

216
00:14:06,050 --> 00:14:06,920
This is the index.

217
00:14:07,220 --> 00:14:09,500
And you will write the code for this function.

218
00:14:09,950 --> 00:14:13,580
Much to sort of that is so your edit it will be sorted.

219
00:14:13,790 --> 00:14:14,320
Simple.

220
00:14:15,020 --> 00:14:20,990
So what you need to do, just write the code for this Margery's function and write the code for this

221
00:14:21,470 --> 00:14:21,920
function.

222
00:14:22,370 --> 00:14:26,810
I hope you can do this because we have done many problems of recursion, so I hope you will be able

223
00:14:26,810 --> 00:14:27,700
to do it properly.

224
00:14:29,480 --> 00:14:34,430
So this is it from this video in the next we do, I will write the code for the Mod, so I will see

225
00:14:34,430 --> 00:14:35,160
you in the next one.

226
00:14:35,480 --> 00:14:36,050
Thank you.

227
00:14:36,200 --> 00:14:36,670
Bye bye.