1
00:00:00,360 --> 00:00:01,490
- [Instructor] Hi.

2
00:00:01,490 --> 00:00:05,840
Now in the previous video,
we introduced merge sort.

3
00:00:05,840 --> 00:00:07,930
And merge sort is a very different kind

4
00:00:07,930 --> 00:00:10,030
of algorithm than we've seen before.

5
00:00:10,030 --> 00:00:12,160
It's a divide and conquer algorithm

6
00:00:12,160 --> 00:00:14,163
that recursively calls itself.

7
00:00:15,100 --> 00:00:17,760
And in so doing, it
divides the input vector

8
00:00:17,760 --> 00:00:19,820
into smaller and smaller vectors,

9
00:00:19,820 --> 00:00:22,070
these are the sub-problems,

10
00:00:22,070 --> 00:00:25,730
and the base cases where a
vector has just one element.

11
00:00:25,730 --> 00:00:28,390
Now one element is already sorted.

12
00:00:28,390 --> 00:00:30,370
And so where does the real work happen?

13
00:00:30,370 --> 00:00:32,470
The real work happens when we merge.

14
00:00:32,470 --> 00:00:34,780
We take those smaller vectors,

15
00:00:34,780 --> 00:00:37,320
each one is already sorted,

16
00:00:37,320 --> 00:00:41,100
and we merge them to produce
another sorted vector

17
00:00:41,100 --> 00:00:42,593
that's a partial solution.

18
00:00:43,490 --> 00:00:45,640
And the last two vectors that we wind

19
00:00:45,640 --> 00:00:48,593
up merging produce the final solution.

20
00:00:49,910 --> 00:00:51,760
Now, what we're gonna do here

21
00:00:51,760 --> 00:00:55,570
is we're gonna implement
merge sort in C++.

22
00:00:55,570 --> 00:00:58,890
I want to point out a
couple of things first.

23
00:00:58,890 --> 00:01:00,540
One is that it's a little wasteful

24
00:01:00,540 --> 00:01:02,950
for us to keep creating new vectors.

25
00:01:02,950 --> 00:01:06,730
Every time we create a new
vector, there is some overhead

26
00:01:06,730 --> 00:01:09,540
and memory that needs to be allocated.

27
00:01:09,540 --> 00:01:11,470
And so what we're gonna do here

28
00:01:11,470 --> 00:01:15,580
is rather than creating new
vectors every time we divide

29
00:01:15,580 --> 00:01:19,460
the vector into smaller
and smaller pieces,

30
00:01:19,460 --> 00:01:22,143
we're just gonna subdivide
our input vector.

31
00:01:23,810 --> 00:01:25,350
And that's easy to do so long

32
00:01:25,350 --> 00:01:28,200
as we have a few indices
indicating the start

33
00:01:28,200 --> 00:01:30,480
and end of each segment.

34
00:01:30,480 --> 00:01:32,890
We're also gonna create
one temporary vector

35
00:01:32,890 --> 00:01:34,340
for our working space.

36
00:01:34,340 --> 00:01:37,600
You'll recall that a merge
sort has a space complexity

37
00:01:37,600 --> 00:01:39,380
of O of n,

38
00:01:39,380 --> 00:01:41,550
which means we need
working space equivalent

39
00:01:41,550 --> 00:01:43,660
to the size of our input.

40
00:01:43,660 --> 00:01:45,800
So we're gonna create a temporary vector

41
00:01:45,800 --> 00:01:47,770
that's gonna hold our merged results,

42
00:01:47,770 --> 00:01:50,440
and we're gonna pass that
around by references needed.

43
00:01:50,440 --> 00:01:53,870
And so keeping those two things in mind,

44
00:01:53,870 --> 00:01:56,793
that's how we're going to
implement merge sort here.

45
00:02:00,440 --> 00:02:03,310
So let's get to coding merge sort.

46
00:02:03,310 --> 00:02:07,800
We'll start with a new C++ file.

47
00:02:07,800 --> 00:02:09,050
We'll call it merge sort.

48
00:02:13,480 --> 00:02:18,480
And we're gonna need vector, obviously.

49
00:02:22,720 --> 00:02:24,750
And we're gonna need iostream

50
00:02:29,860 --> 00:02:31,210
so we can print things out.

51
00:02:32,770 --> 00:02:37,330
And then, let's also
borrow some code here.

52
00:02:37,330 --> 00:02:40,763
I've got this print vector
function that we've used before.

53
00:02:41,730 --> 00:02:43,573
I'm just gonna copy and paste that.

54
00:02:44,880 --> 00:02:49,880
And then let's start off with placeholders

55
00:02:49,970 --> 00:02:52,400
for the rest of our code.

56
00:02:52,400 --> 00:02:56,223
We're going to have a merge sort function.

57
00:03:00,220 --> 00:03:02,790
And I think we're gonna implement this

58
00:03:02,790 --> 00:03:05,393
with a separate function for merge.

59
00:03:08,150 --> 00:03:09,363
Now we're going to,

60
00:03:11,420 --> 00:03:13,170
and then we're also gonna have main

61
00:03:17,010 --> 00:03:18,853
where we can run and test our code.

62
00:03:21,830 --> 00:03:26,030
All right, so what do merge
sort and merge look like?

63
00:03:26,030 --> 00:03:28,970
Well, let's start with a merge sort.

64
00:03:28,970 --> 00:03:30,000
It's gonna be templated.

65
00:03:30,000 --> 00:03:32,703
So I'm just gonna borrow
this template and code here.

66
00:03:34,900 --> 00:03:38,680
And what are the inputs to merge sort?

67
00:03:38,680 --> 00:03:42,130
We're going to need the input vector.

68
00:03:42,130 --> 00:03:46,433
So standard vector of comparables.

69
00:03:50,550 --> 00:03:51,683
And we'll call that V.

70
00:03:53,150 --> 00:03:56,060
And we're gonna need our
starting and ending positions.

71
00:03:56,060 --> 00:04:01,060
So two indices, int, start, int, end.

72
00:04:02,670 --> 00:04:04,770
And we're gonna need that temporary vector

73
00:04:11,220 --> 00:04:13,283
which is also a vector of comparables.

74
00:04:14,240 --> 00:04:15,490
And we'll call that temp.

75
00:04:17,380 --> 00:04:20,990
So that's our signature for merge sort.

76
00:04:20,990 --> 00:04:23,060
We'll get to the body in a second.

77
00:04:23,060 --> 00:04:28,050
And let's flesh out the
signature for merge.

78
00:04:28,050 --> 00:04:29,310
So when we merge,

79
00:04:29,310 --> 00:04:33,800
we're also going to have
to pass in an input vector

80
00:04:33,800 --> 00:04:38,800
which is also gonna be of comparables.

81
00:04:40,360 --> 00:04:41,463
And we'll call that V.

82
00:04:44,170 --> 00:04:46,600
But remember, here in merge, we're dealing

83
00:04:46,600 --> 00:04:50,630
with a left-hand subvector
and a right-hand subvector.

84
00:04:50,630 --> 00:04:53,440
And so we're going to need
to know where each one

85
00:04:53,440 --> 00:04:55,400
of those begins and ends.

86
00:04:55,400 --> 00:04:59,590
So we're gonna have to
have three indices here,

87
00:04:59,590 --> 00:05:00,893
int start,

88
00:05:01,870 --> 00:05:05,657
int middle and int end.

89
00:05:07,601 --> 00:05:09,470
And you're gonna say, "Hey, wait a minute.

90
00:05:09,470 --> 00:05:10,540
That's only three."

91
00:05:10,540 --> 00:05:13,420
But each subvector is going
to have a starting point

92
00:05:13,420 --> 00:05:14,410
and an ending point.

93
00:05:14,410 --> 00:05:18,080
Well, the first subvector, the subvector

94
00:05:18,080 --> 00:05:20,933
on the left is gonna run
from start to middle.

95
00:05:22,000 --> 00:05:25,000
The subvector on the right is gonna run

96
00:05:25,000 --> 00:05:27,390
from middle plus one to end.

97
00:05:27,390 --> 00:05:30,350
So we don't need to pass in four integers.

98
00:05:30,350 --> 00:05:34,030
We know that the right-hand subvector

99
00:05:34,030 --> 00:05:36,070
is always gonna start at middle plus one.

100
00:05:36,070 --> 00:05:37,830
So we have those three,

101
00:05:37,830 --> 00:05:39,680
and then we're gonna
need our temporary vector

102
00:05:39,680 --> 00:05:42,080
to hold our merge results.

103
00:05:42,080 --> 00:05:45,623
Standard vector of comparables.

104
00:05:50,240 --> 00:05:51,873
And we'll call that temp.

105
00:05:53,600 --> 00:05:57,730
And so that's what merge
is gonna look like,

106
00:05:57,730 --> 00:06:00,230
as far as the signature goes.

107
00:06:00,230 --> 00:06:02,370
So let's start to flesh
these out a little bit.

108
00:06:02,370 --> 00:06:03,933
Let's start with merge sort.

109
00:06:05,010 --> 00:06:08,770
And you recall, this is a
divide and conquer algorithm.

110
00:06:08,770 --> 00:06:10,670
It's a recursive algorithm.

111
00:06:10,670 --> 00:06:12,920
It's gonna call itself.

112
00:06:12,920 --> 00:06:15,970
And whenever we have
a recursive algorithm,

113
00:06:15,970 --> 00:06:18,720
we have recursive cases
and we have a base case.

114
00:06:18,720 --> 00:06:21,100
We have to have at least one base case.

115
00:06:21,100 --> 00:06:23,683
So we have some point where
we stop our recursion.

116
00:06:24,730 --> 00:06:28,360
And so the base case, as I've said before,

117
00:06:28,360 --> 00:06:30,890
is when we have a one-element vector

118
00:06:30,890 --> 00:06:34,000
because one element is
sorted by definition.

119
00:06:34,000 --> 00:06:36,030
So if

120
00:06:37,840 --> 00:06:40,843
end equal start,

121
00:06:42,320 --> 00:06:44,273
then we have just one element.

122
00:06:45,270 --> 00:06:47,730
And we're gonna do something here.

123
00:06:47,730 --> 00:06:49,173
This is our base case.

124
00:06:50,970 --> 00:06:52,810
What do we do?

125
00:06:52,810 --> 00:06:53,970
Well, it's already sorted.

126
00:06:53,970 --> 00:06:55,320
So we're just gonna return.

127
00:06:56,360 --> 00:06:57,680
And then we need to deal with all

128
00:06:57,680 --> 00:07:02,680
of our other cases where
end is greater than start.

129
00:07:03,130 --> 00:07:07,810
Let's just make this all inclusive here.

130
00:07:07,810 --> 00:07:09,910
So end less than or equal to start.

131
00:07:09,910 --> 00:07:14,840
And so all of our else cases will be cases

132
00:07:14,840 --> 00:07:17,180
where end is greater than start,

133
00:07:17,180 --> 00:07:19,940
meaning that we have two or more elements.

134
00:07:19,940 --> 00:07:23,373
So this is where our
recursive cases will go.

135
00:07:27,700 --> 00:07:28,720
And what do we do?

136
00:07:28,720 --> 00:07:33,440
Well, we're gonna divide and conquer.

137
00:07:33,440 --> 00:07:36,740
And the division is pretty simple.

138
00:07:36,740 --> 00:07:39,400
All we need to do is find the middle

139
00:07:39,400 --> 00:07:43,670
of our input range and subdivide.

140
00:07:43,670 --> 00:07:45,340
So int middle

141
00:07:47,100 --> 00:07:51,370
equal start plus end

142
00:07:54,040 --> 00:07:54,873
divided by two.

143
00:07:55,840 --> 00:07:57,830
Now this is integer division.

144
00:07:57,830 --> 00:08:00,350
So if we're dividing an odd number,

145
00:08:00,350 --> 00:08:01,550
this is gonna truncate.

146
00:08:01,550 --> 00:08:03,200
If we're dividing an even number,

147
00:08:03,200 --> 00:08:04,800
we don't need to truncate.

148
00:08:04,800 --> 00:08:07,230
And so that gives us our middle.

149
00:08:07,230 --> 00:08:10,853
And then we're gonna make two
recursive calls to merge sort.

150
00:08:12,650 --> 00:08:14,580
So it's gonna call itself

151
00:08:14,580 --> 00:08:19,580
with V and start to middle,

152
00:08:20,770 --> 00:08:22,363
sorry, middle.

153
00:08:25,260 --> 00:08:27,900
So that's the first recursive call.

154
00:08:27,900 --> 00:08:29,930
It's dealing with the left-hand side

155
00:08:29,930 --> 00:08:33,100
which is going from start to middle.

156
00:08:33,100 --> 00:08:36,017
And then we're gonna make a call to deal

157
00:08:38,410 --> 00:08:40,760
with the right-hand side.

158
00:08:40,760 --> 00:08:42,690
And remember, we said middle plus one

159
00:08:45,430 --> 00:08:46,263
to the end.

160
00:08:47,648 --> 00:08:51,060
Okay. But I've left out the temporary.

161
00:08:51,060 --> 00:08:52,883
I need to pass in the temporary.

162
00:09:02,190 --> 00:09:04,530
That's gonna hold our merge results.

163
00:09:04,530 --> 00:09:06,830
And then we merge

164
00:09:11,690 --> 00:09:13,000
with our vector.

165
00:09:13,000 --> 00:09:13,833
Start,

166
00:09:14,840 --> 00:09:15,673
middle,

167
00:09:16,632 --> 00:09:17,632
end, simple.

168
00:09:20,690 --> 00:09:22,430
So let's see what we're doing here.

169
00:09:22,430 --> 00:09:25,383
We're finding, let me back up.

170
00:09:26,560 --> 00:09:30,600
These are the cases where
end is greater than start.

171
00:09:30,600 --> 00:09:33,920
Meaning that we have two or more elements.

172
00:09:33,920 --> 00:09:37,653
We find the middle so we can subdivide.

173
00:09:38,620 --> 00:09:41,500
Then we make recursive calls

174
00:09:41,500 --> 00:09:45,070
on the two subvectors that we get

175
00:09:45,070 --> 00:09:47,023
by dividing it at the middle.

176
00:09:47,960 --> 00:09:51,483
And then when we're done,
we merge the results.

177
00:09:52,350 --> 00:09:54,323
That's all there is to merge sort.

178
00:09:55,570 --> 00:09:59,550
Now we have to deal with
this function here, merge.

179
00:09:59,550 --> 00:10:01,880
And you'll recall that I said merge

180
00:10:01,880 --> 00:10:03,930
is at the heart of this algorithm.

181
00:10:03,930 --> 00:10:06,530
And so this is where the
real work is gonna be done.

182
00:10:08,230 --> 00:10:10,423
So now let's complete this merge function.

183
00:10:11,510 --> 00:10:15,640
We have as inputs,
vector of comparables, V.

184
00:10:15,640 --> 00:10:17,530
We have start, middle, and end

185
00:10:17,530 --> 00:10:20,230
which indicate where the left-hand side

186
00:10:20,230 --> 00:10:22,780
and the right-hand side start and end.

187
00:10:22,780 --> 00:10:25,230
And we have this temporary
vector that we'll use

188
00:10:25,230 --> 00:10:27,603
to hold our results while we're merging.

189
00:10:28,681 --> 00:10:33,681
So first, we will
initialize a few variables,

190
00:10:34,130 --> 00:10:37,263
int i equals start.

191
00:10:38,890 --> 00:10:43,757
Now i is gonna be the
index into the left half.

192
00:10:51,100 --> 00:10:56,100
Int j is gonna keep one middle plus one.

193
00:10:59,700 --> 00:11:02,810
That's our first position
on the right-hand side,

194
00:11:02,810 --> 00:11:04,203
that's the index.

195
00:11:05,970 --> 00:11:07,993
And to do the right half.

196
00:11:11,040 --> 00:11:15,053
And int k equals zero.

197
00:11:16,750 --> 00:11:21,750
And that's an index,
whoops, a temporary vector.

198
00:11:27,710 --> 00:11:31,570
And we could call these
left index, right index,

199
00:11:31,570 --> 00:11:33,320
and temp index.

200
00:11:33,320 --> 00:11:35,830
I think it's easier to
work with i, j, and k,

201
00:11:35,830 --> 00:11:39,520
but if you want to download
the code and fiddle with it,

202
00:11:39,520 --> 00:11:41,563
please feel free to change these names.

203
00:11:43,160 --> 00:11:46,980
And then remember that
we have a couple of cases

204
00:11:46,980 --> 00:11:48,550
we need to look at.

205
00:11:48,550 --> 00:11:52,080
While we have values in the left-hand side

206
00:11:52,080 --> 00:11:54,820
and the right-hand that
we haven't consumed,

207
00:11:54,820 --> 00:11:57,290
we need to be doing some comparisons.

208
00:11:57,290 --> 00:12:00,000
And then we're gonna
have other cases where

209
00:12:00,000 --> 00:12:02,480
we've consumed all the
values on the left-hand side,

210
00:12:02,480 --> 00:12:04,970
or we've consumed all the
values on the right-hand side.

211
00:12:04,970 --> 00:12:06,280
But let's start with the case

212
00:12:06,280 --> 00:12:08,053
where we have to make comparisons.

213
00:12:09,230 --> 00:12:14,230
And so, while i is less
than or equal to middle,

214
00:12:17,760 --> 00:12:22,760
that is, we haven't used up
all of the left-hand side,

215
00:12:22,820 --> 00:12:27,820
and j is less than or equal to end,

216
00:12:28,010 --> 00:12:33,010
we haven't used up all the
values on the right-hand side.

217
00:12:33,160 --> 00:12:35,520
Then we perform a comparison.

218
00:12:35,520 --> 00:12:39,180
If v sub i

219
00:12:41,700 --> 00:12:43,490
less than or equal

220
00:12:43,490 --> 00:12:47,560
to v sub j if the value that we're looking

221
00:12:47,560 --> 00:12:50,600
at on the left-hand side
is less than or equal

222
00:12:50,600 --> 00:12:53,490
to the value that we see
on the right-hand side,

223
00:12:53,490 --> 00:12:55,630
then we're gonna use that value.

224
00:12:55,630 --> 00:13:00,630
So temp k is going to take
the value from v sub i.

225
00:13:04,700 --> 00:13:08,810
Okay. And then we need
to increment our indices.

226
00:13:08,810 --> 00:13:13,213
Plus, plus K and plus, plus i.

227
00:13:16,960 --> 00:13:19,593
Otherwise, else.

228
00:13:21,840 --> 00:13:26,270
And in this case, we have
the value on the left

229
00:13:26,270 --> 00:13:28,140
is greater than the value on the right.

230
00:13:28,140 --> 00:13:30,900
So we're gonna want to take
the value on the right,

231
00:13:30,900 --> 00:13:35,900
temp sub k gets the value on the right.

232
00:13:36,720 --> 00:13:38,813
That's v sub j.

233
00:13:40,020 --> 00:13:43,610
And then we increment our indices again.

234
00:13:43,610 --> 00:13:44,603
Plus, plus k,

235
00:13:46,110 --> 00:13:48,453
and plus, plus j this time.

236
00:13:50,140 --> 00:13:50,973
Okay.

237
00:13:53,300 --> 00:13:55,593
So that's when we're
performing comparisons.

238
00:13:56,450 --> 00:13:58,380
It would take, this case,

239
00:13:58,380 --> 00:14:00,000
the value from the left,

240
00:14:00,000 --> 00:14:03,100
in this case, we're gonna
take the value from the right.

241
00:14:03,100 --> 00:14:04,480
Okay.

242
00:14:04,480 --> 00:14:07,720
Now we have to deal with the
cases where we've consumed

243
00:14:07,720 --> 00:14:09,460
one side or the other.

244
00:14:09,460 --> 00:14:13,800
So let's look at the left-hand side first.

245
00:14:13,800 --> 00:14:18,800
While i less than or equal to middle,

246
00:14:20,600 --> 00:14:22,313
we still have stuff there.

247
00:14:23,940 --> 00:14:28,940
Then temp k is going to get v sub i.

248
00:14:34,580 --> 00:14:38,540
And then we're going
to increment k to point

249
00:14:38,540 --> 00:14:41,770
to the next available
position in our vector

250
00:14:41,770 --> 00:14:45,843
and increment i.

251
00:14:47,040 --> 00:14:50,140
And all this is gonna do
is it's just gonna continue

252
00:14:50,140 --> 00:14:54,470
through the left-hand subvector

253
00:14:54,470 --> 00:14:56,530
until it's copied all of the values

254
00:14:56,530 --> 00:14:58,163
into the temporary vector.

255
00:14:59,230 --> 00:15:03,290
And then we have the case while j, sorry

256
00:15:06,510 --> 00:15:08,443
less than or equal to end.

257
00:15:10,460 --> 00:15:12,280
We're gonna do the same thing.

258
00:15:12,280 --> 00:15:17,280
Temp k is gonna take v sub j this time.

259
00:15:20,820 --> 00:15:22,973
That's the value from the right-hand side.

260
00:15:24,180 --> 00:15:25,163
Increment k.

261
00:15:27,170 --> 00:15:28,003
Increment j.

262
00:15:31,060 --> 00:15:32,113
So we're almost done.

263
00:15:33,840 --> 00:15:36,320
You see, we're initializing
our values here

264
00:15:36,320 --> 00:15:38,990
for where our indices are,

265
00:15:38,990 --> 00:15:42,483
the points of interest in
the subvectors in question.

266
00:15:43,490 --> 00:15:45,920
We're handling the case
where we have values

267
00:15:45,920 --> 00:15:48,230
on both the left and the right

268
00:15:48,230 --> 00:15:49,740
and choosing the lesser

269
00:15:49,740 --> 00:15:54,740
and putting it into the temporary vector.

270
00:15:55,210 --> 00:15:58,040
Here, we have the cases
where we've consumed

271
00:15:58,040 --> 00:15:59,100
one side or the other,

272
00:15:59,100 --> 00:16:01,850
and we're just continuing
to consume values

273
00:16:01,850 --> 00:16:03,040
from the appropriate side

274
00:16:03,040 --> 00:16:05,380
and put them into our temporary vector.

275
00:16:05,380 --> 00:16:07,530
And then before we finish,

276
00:16:07,530 --> 00:16:12,453
we want to copy everything
back to our vector v.

277
00:16:13,300 --> 00:16:18,040
So for int i equals zero,

278
00:16:22,290 --> 00:16:24,380
notice, this is a different i

279
00:16:24,380 --> 00:16:26,530
from the one above,
it's within this scope.

280
00:16:26,530 --> 00:16:31,530
I less than or equal to end minus start.

281
00:16:37,170 --> 00:16:38,323
Plus, plus i.

282
00:16:41,170 --> 00:16:42,950
We're just gonna copy our values over.

283
00:16:42,950 --> 00:16:47,460
So v start, plus i.

284
00:16:47,460 --> 00:16:49,223
Remember, i could be zero.

285
00:16:50,120 --> 00:16:51,850
Equal temp i.

286
00:16:54,780 --> 00:16:58,720
And that'll copy our sorted
values that we've built

287
00:16:58,720 --> 00:17:03,720
in our temporary vector into
the appropriate positions in v.

288
00:17:03,951 --> 00:17:04,784
All right?

289
00:17:04,784 --> 00:17:06,610
And that completes our implementation

290
00:17:06,610 --> 00:17:09,640
of this merge function, which is again,

291
00:17:09,640 --> 00:17:12,140
called after we get the results back

292
00:17:12,140 --> 00:17:15,093
from these recursive calls to merge sort.

293
00:17:16,220 --> 00:17:20,070
So I think that's our implementation.

294
00:17:20,070 --> 00:17:21,893
Let's test it out.

295
00:17:23,090 --> 00:17:27,383
So in order to test it out,
we're gonna need a vector.

296
00:17:32,800 --> 00:17:34,500
And we'll make this vector of int,

297
00:17:36,300 --> 00:17:37,463
and we'll call it v.

298
00:17:38,680 --> 00:17:40,270
And we'll put in some ints.

299
00:17:42,221 --> 00:17:44,698
41, 13,

300
00:17:44,698 --> 00:17:47,333
28,

301
00:17:47,333 --> 00:17:49,647
35,

302
00:17:49,647 --> 00:17:52,026
90,

303
00:17:52,026 --> 00:17:52,859
34,

304
00:17:54,088 --> 00:17:54,921
67,

305
00:17:56,364 --> 00:17:57,197
72,

306
00:18:00,867 --> 00:18:01,700
56,

307
00:18:02,685 --> 00:18:03,518
30,

308
00:18:04,666 --> 00:18:05,499
78,

309
00:18:06,725 --> 00:18:07,558
19,

310
00:18:08,804 --> 00:18:09,637
48,

311
00:18:10,670 --> 00:18:12,330
20,

312
00:18:12,330 --> 00:18:13,500
55,

313
00:18:13,500 --> 00:18:15,320
and say 61.

314
00:18:15,320 --> 00:18:19,800
Okay, now, I've put down 16 numbers here

315
00:18:19,800 --> 00:18:22,900
because I want nice pretty formatting

316
00:18:22,900 --> 00:18:25,410
for something I'm gonna
show you a little later.

317
00:18:25,410 --> 00:18:27,750
Obviously, merge sort will work

318
00:18:27,750 --> 00:18:29,250
with any number.

319
00:18:29,250 --> 00:18:32,063
It doesn't need to be an even
number or a power of two.

320
00:18:33,400 --> 00:18:34,940
So just keep that in mind.

321
00:18:34,940 --> 00:18:37,670
This is just for demonstration purposes,

322
00:18:37,670 --> 00:18:41,250
but we could put in any
vector ints or any vector

323
00:18:41,250 --> 00:18:43,710
of comparables, for example.

324
00:18:43,710 --> 00:18:47,700
And we're gonna need a
temporary vector, std.

325
00:18:47,700 --> 00:18:48,833
Whoops, vector.

326
00:18:50,630 --> 00:18:52,580
And this will also be a vector of ints,

327
00:18:53,510 --> 00:18:55,420
and we'll call it temp.

328
00:18:55,420 --> 00:18:58,370
And we're gonna make
this vector the same size

329
00:19:00,473 --> 00:19:02,470
as our data.

330
00:19:02,470 --> 00:19:04,890
Okay, so now we have a temporary vector.

331
00:19:04,890 --> 00:19:06,243
It's the same size as v.

332
00:19:08,760 --> 00:19:12,140
And now let's call that
print vector function

333
00:19:13,820 --> 00:19:15,670
that I copied at the very beginning

334
00:19:15,670 --> 00:19:18,280
of the video, int print v,

335
00:19:18,280 --> 00:19:20,530
that'll print the unsorted vector.

336
00:19:20,530 --> 00:19:22,180
And then we'll call a merge sort.

337
00:19:24,447 --> 00:19:26,790
And now here, we're
gonna provide it with v.

338
00:19:26,790 --> 00:19:30,130
And we're gonna want to
span over the entire range.

339
00:19:30,130 --> 00:19:33,780
Remember, that merge sort
takes a start and an end.

340
00:19:33,780 --> 00:19:37,480
So this is gonna range
over the entire vector.

341
00:19:37,480 --> 00:19:41,000
So that's v size

342
00:19:42,830 --> 00:19:43,763
minus one,

343
00:19:44,630 --> 00:19:47,080
and we're gonna pass in
that temporary vector too

344
00:19:48,810 --> 00:19:53,360
Okay. And then when we're
done, print vector v.

345
00:19:57,270 --> 00:19:59,760
Now, unless I've made some typos,

346
00:19:59,760 --> 00:20:01,230
that should run quite nicely.

347
00:20:01,230 --> 00:20:02,453
So let's give it a run.

348
00:20:04,552 --> 00:20:05,385
And we build it.

349
00:20:09,410 --> 00:20:10,243
And run it.

350
00:20:10,243 --> 00:20:12,350
And that's exactly what
we expected to happen.

351
00:20:12,350 --> 00:20:17,000
Here's our input vector 41, 13, 28, so on.

352
00:20:17,000 --> 00:20:22,000
As I have up here and
here is our sorted vector

353
00:20:22,350 --> 00:20:26,493
in the end 13, 19, 20, 28, 30 and so on.

354
00:20:27,450 --> 00:20:29,750
And that looks like it's
working as it should.

355
00:20:31,240 --> 00:20:34,530
Now, before we wrap up, I
want to just do one more thing

356
00:20:34,530 --> 00:20:38,010
to give you a little more
insight into how this works

357
00:20:38,010 --> 00:20:41,820
as merge sort is doing its work.

358
00:20:41,820 --> 00:20:46,820
So I'm gonna create a new function here.

359
00:20:49,650 --> 00:20:51,060
It will also be templated.

360
00:20:51,060 --> 00:20:52,560
So I'm gonna borrow this code.

361
00:20:53,850 --> 00:20:58,370
And it's just gonna print a
selected range of elements

362
00:20:58,370 --> 00:21:01,810
within a vector and then
print a white space padding

363
00:21:01,810 --> 00:21:03,160
for the rest.

364
00:21:03,160 --> 00:21:07,703
So void, and we'll call
this print vector segment.

365
00:21:13,000 --> 00:21:13,833
And

366
00:21:19,200 --> 00:21:20,563
it's gonna take a vector,

367
00:21:26,520 --> 00:21:27,743
both comparables.

368
00:21:30,610 --> 00:21:32,123
And we can call that v.

369
00:21:34,050 --> 00:21:38,893
But it's also gonna take
two integers, int start,

370
00:21:40,510 --> 00:21:41,527
int end.

371
00:21:44,040 --> 00:21:47,880
So that it's going to print
the elements between start

372
00:21:47,880 --> 00:21:50,920
and end inclusive and
print white space padding

373
00:21:50,920 --> 00:21:53,249
for the other positions.

374
00:21:53,249 --> 00:21:58,249
So little for loop for int i equals zero.

375
00:22:02,340 --> 00:22:07,340
I less than the size of the vector.

376
00:22:11,350 --> 00:22:12,333
Plus, plus i.

377
00:22:14,800 --> 00:22:17,700
And if

378
00:22:19,800 --> 00:22:23,583
i is greater than or equal to start,

379
00:22:25,350 --> 00:22:29,920
and i less than or equal, oops,

380
00:22:29,920 --> 00:22:31,530
equal to end,

381
00:22:31,530 --> 00:22:34,823
if it's in that range,
we're gonna print the value.

382
00:22:42,910 --> 00:22:44,693
And a little white space.

383
00:22:47,060 --> 00:22:49,263
Otherwise, else,

384
00:22:54,550 --> 00:22:56,550
we're just gonna print some white space.

385
00:23:00,060 --> 00:23:00,893
All right.

386
00:23:00,893 --> 00:23:05,040
And when we're all done,
oops, when we're all done,

387
00:23:05,040 --> 00:23:07,523
we're going to print an inline character.

388
00:23:20,270 --> 00:23:21,103
I had that right.

389
00:23:21,103 --> 00:23:21,936
There we go.

390
00:23:21,936 --> 00:23:22,860
All right.

391
00:23:22,860 --> 00:23:26,280
So now we have this function,
print vector segment.

392
00:23:26,280 --> 00:23:27,890
And now, where are we gonna use it?

393
00:23:27,890 --> 00:23:31,483
I'm gonna go down to our
merge sort algorithm.

394
00:23:33,120 --> 00:23:35,150
We've calculated middle at this point,

395
00:23:35,150 --> 00:23:38,030
you'll recall this is the recursive cases

396
00:23:38,030 --> 00:23:39,780
and we have to calculate middle

397
00:23:39,780 --> 00:23:43,410
and split our vector into subvectors.

398
00:23:43,410 --> 00:23:46,473
So we're going to say print,

399
00:23:47,850 --> 00:23:50,173
that's print vector segment.

400
00:23:52,750 --> 00:23:56,623
V start, middle.

401
00:23:58,430 --> 00:24:01,793
That's printing the left-hand side.

402
00:24:02,850 --> 00:24:07,850
And then here, we will
print vector segment.

403
00:24:14,760 --> 00:24:18,547
The middle plus one to end.

404
00:24:22,940 --> 00:24:27,940
And then after we merge
again, print, vector, segment

405
00:24:29,450 --> 00:24:32,633
v start, end.

406
00:24:34,170 --> 00:24:37,010
And now we'll get a little more insight

407
00:24:37,010 --> 00:24:38,550
into how this is working.

408
00:24:38,550 --> 00:24:40,270
Let's just think about this for a second.

409
00:24:40,270 --> 00:24:45,040
We're going to split
some vector or subvector

410
00:24:45,040 --> 00:24:47,610
into smaller pieces.

411
00:24:47,610 --> 00:24:52,040
And so we're going to see the
left-hand side printed first,

412
00:24:52,040 --> 00:24:56,160
and the right-hand side printed second.

413
00:24:56,160 --> 00:24:58,070
And then after the merge takes place,

414
00:24:58,070 --> 00:25:00,270
we'll see the merge result.

415
00:25:00,270 --> 00:25:05,270
But notice that these
recursive calls might continue

416
00:25:07,650 --> 00:25:09,320
before we get back to merging.

417
00:25:09,320 --> 00:25:11,740
So let's run this and see what happens

418
00:25:15,020 --> 00:25:16,763
And hopefully, there are no typos.

419
00:25:18,320 --> 00:25:19,210
Yay. Okay.

420
00:25:19,210 --> 00:25:20,593
So that's what I expected.

421
00:25:21,740 --> 00:25:24,150
So let's just take a look here real quick.

422
00:25:24,150 --> 00:25:26,623
So this is our input vector here.

423
00:25:28,730 --> 00:25:33,280
And we split it and we print it.

424
00:25:33,280 --> 00:25:36,523
We print this left-hand
side, that's the left half.

425
00:25:37,500 --> 00:25:39,490
And then we make another recursive call,

426
00:25:39,490 --> 00:25:41,090
and we print the left half,

427
00:25:41,090 --> 00:25:42,433
and another recursive call.

428
00:25:42,433 --> 00:25:45,440
You can print the left half
and another recursive call.

429
00:25:45,440 --> 00:25:46,380
We print the left half.

430
00:25:46,380 --> 00:25:48,010
Now this is a base case.

431
00:25:48,010 --> 00:25:49,060
So there aren't gonna be any more

432
00:25:49,060 --> 00:25:49,973
recursive calls after this.

433
00:25:49,973 --> 00:25:51,910
This is a one element vector

434
00:25:51,910 --> 00:25:54,670
or subvector as the case may be.

435
00:25:54,670 --> 00:25:58,190
And so then we're gonna start
processing the right-hand side

436
00:25:58,190 --> 00:25:59,383
and we get 13.

437
00:26:00,360 --> 00:26:03,800
And then we merge those
two values into 13 and 41.

438
00:26:03,800 --> 00:26:08,010
And now, this was the right-hand side.

439
00:26:08,010 --> 00:26:11,400
So here's the right-hand
side being split off

440
00:26:11,400 --> 00:26:16,400
and the base cases of the
recursion and the merge.

441
00:26:18,360 --> 00:26:23,360
And then this here gets merged
with this to produce this.

442
00:26:28,140 --> 00:26:30,480
So 13 from the left,

443
00:26:30,480 --> 00:26:32,030
28 from the right,

444
00:26:32,030 --> 00:26:33,530
35 from the right,

445
00:26:33,530 --> 00:26:35,930
41 from the left.

446
00:26:35,930 --> 00:26:38,920
And now we process the right-hand side

447
00:26:38,920 --> 00:26:42,120
because of course, these
come in an order here.

448
00:26:42,120 --> 00:26:44,730
And the same thing
happens, we keep splitting

449
00:26:44,730 --> 00:26:46,250
until we hit those base cases.

450
00:26:46,250 --> 00:26:49,540
We do a merge of one element each

451
00:26:49,540 --> 00:26:51,820
to make a two-element sub vector.

452
00:26:51,820 --> 00:26:54,630
Do the same thing for the right hand side.

453
00:26:54,630 --> 00:26:56,450
We merge those results.

454
00:26:56,450 --> 00:26:58,440
And so we've completed the process here

455
00:26:58,440 --> 00:27:00,880
for the left-hand subvector.

456
00:27:00,880 --> 00:27:01,860
And then we do the whole thing,

457
00:27:01,860 --> 00:27:04,300
same way for the right-hand subvector.

458
00:27:04,300 --> 00:27:05,670
And you can see how that works.

459
00:27:05,670 --> 00:27:07,620
So I hope that gives you
a little more insight

460
00:27:07,620 --> 00:27:09,403
into how merge sort works.

461
00:27:10,260 --> 00:27:12,160
Source code is on Blackboard.

462
00:27:12,160 --> 00:27:13,253
Thank you very much.