Original subtitles

1 1

(futuristic electronic music) 2

2

(keyboard keys clack) 3

3

All right, in this video, 4

4

we're going to look at merge sort. 5

5

Now, merge sort is a divide and conquer algorithm 6

6

because it involves splitting the array you wanna sort 7

7

into a bunch of smaller arrays, 8

8

and it's usually implemented using recursion. 9

9

You can write algorithm using loops, 10

10

but it's usually written recursively. 11

11

Merge sort involves two major phases. 12

12

The first phase is the splitting phase, 13

13

and second phase is the merging phase. 14

14

We do the sorting during the merging phase. 15

15

The splitting phase is a preparation phase 16

16

to make sorting faster during the merging phase. 17

17

Now, I wanna make it clear that the splitting is logical. 18

18

We don't create new arrays when we do the splitting. 19

19

We use indices to keep track of 20

20

where the array has been split. 21

21

So when during the splitting phase, 22

22

we're not actually creating new array instances. 23

23

So let's look at the splitting phase. 24

24

In the splitting phase, we start with the unsorted array, 25

25

and we divide the array into two arrays, 26

26

and remember, both of the arrays will be unsorted, 27

27

and we call the first array, the left array 28

28

and second array, the right array, 29

29

and we generally just divide the array down the middle. 30

30

If you have an odd number of elements, 31

31

it will depend on the implementation. 32

32

Some implementation will put the extra element 33

33

into the left array, 34

34

and some implementations will put the extra element 35

35

into the right array, 36

36

but the important point is you're dividing the array 37

37

or splitting the array into two arrays, 38

38

the left array and the right array, 39

39

and then, once you've done that, 40

40

you keep splitting down even further. 41

41

So now you go to the left array, 42

42

and you split that into a left and a right array, 43

43

and then, you split that left array 44

44

into a left and a right array, and you keep going, 45

45

splitting all the arrays and the sub-arrays 46

46

until you split the original array 47

47

into a bunch of one-element arrays, 48

48

and remember from our discussion of insertion sort, 49

49

a one-element array is sorted by default 50

50

because there's only one element in it. 51

51

So in the splitting phase, you're taking the array, 52

52

you're dividing it in half, 53

53

and then, you're dividing the two sub-arrays in half, 54

54

and you're dividing those four sub-arrays in half, 55

55

et cetera, 56

56

until you get down to a bunch of one-element arrays, 57

57

and that is the splitting phase. 58

58

Once you've done that, 59

59

you're going to enter the merging phase, 60

60

and in the merging phase, 61

61

you're going to merge every left/right pair 62

62

into a sorted array. 63

63

So let's say we have an array of four elements 64

64

just to explain this. 65

65

So we're gonna split that into two sub-arrays 66

66

of length two each, 67

67

and then, we're gonna split those two sub-arrays 68

68

into two arrays of one element. 69

69

So from that four-element array, 70

70

we're gonna end up with four one-element sub-arrays. 71

71

So we split the original array 72

72

into a left and right sub-array, 73

73

and then, we split the left sub-array into left and right 74

74

and the right sub-array into left and right, 75

75

and then what we do is we take the two one-element arrays 76

76

from the left sub-array, 77

77

and we merge them back into a two-element array. 78

78

The merged two-element array will be sorted, 79

79

so when we do the merge, 80

80

that's the point when we do the sort, 81

81

and then, we'll take the two elements 82

82

from the right sub-array, 83

83

and we'll merge them into a two-element sub-array. 84

84

So now we have, we're back to two arrays, 85

85

a left and a right array, 86

86

except this time, the left and the right array are sorted, 87

87

and then, we'll merge the left and right array, 88

88

which are now two elements each, 89

89

back into a four-element array, 90

90

and at that point, when we do the merge, we sort, 91

91

so we get a four-element array that's sorted, 92

92

and we have sorted our array. 93

93

So basically, we take the bunch of one-element arrays, 94

94

and we keep merging them into two-element, 95

95

four-element, eight-element, et cetera, 96

96

and at each merge, we're making sure 97

97

that the resulting arrays are sorted 98

98

until we've merged all the arrays back into one array, 99

99

and at that point, that array will be sorted 100

100

because when we're merging, we're sorting. 101

101

So every resulting array from the merge will be sorted. 102

102

Now the merging phase does not happen in place. 103

103

It uses temporary arrays. 104

104

So the splitting phase is in place, 105

105

but we need temporary arrays to do the merge. 106

106

So let's look at our usual array here. 107

107

Our start index will be zero. 108

108

Our end will be seven, which is equal to array.length, 109

109

and we're going to get our midpoint 110

110

by dividing start plus end by two, 111

111

so our midpoint will be three, 112

112

and in the implementation I'm going to show you, 113

113

the extra element will go into the right array. 114

114

So the first time we split this array, 115

115

elements zero, one, and two will go into the left array, 116

116

and elements three, four, five, and six 117

117

will go into the right array, 118

118

and so, now, let's split the left array. 119

119

So we're not gonna do anything with the right array 120

120

that's in black now, 121

121

and we're gonna look at the left array, 122

122

and for the left array, the start index is zero, 123

123

and the end index is three. 124

124

The end index is always one greater 125

125

than the index of the last element in the array. 126

126

So once again, we're gonna take the midpoint 127

127

by adding start to end and dividing by two, 128

128

so we'll have three over two which is one, 129

129

and that means that the first element 130

130

is going to go into the left array, 131

131

and elements one to two are going to into the right array, 132

132

and so now, we have this situation. 133

133

Now we have finished splitting 20. 134

134

We can't split that any further. 135

135

It's already a one-element array, 136

136

so we only have to worry at this point 137

137

about splitting the right array. 138

138

So we need to split the array 139

139

that's occupying positions one and two, 140

140

and so the start index is one. 141

141

The end index is three. 142

142

The midpoint will be one plus three over two which is two, 143

143

and so, we're gonna put the first element 144

144

into the left array 145

145

and the second element into the right array, 146

146

and we have now completed splitting the left array 147

147

into one-element arrays. 148

148

Now, one and two are both coloured in a green shade 149

149

because they're actually sibling arrays. 150

150

We go up for a minute. 151

151

The left and right arrays are the sibling arrays. 152

152

So these are the two arrays we're going to merge. 153

153

When we split the left array, 154

154

we ended up with a one-element and two-element array, 155

155

and those arrays are sibling arrays, 156

156

so when we do the merge, 157

157

we'll be merging the array that has 20 158

158

with the array that has 35 and minus 15. 159

159

We were able to split the right array one more time, 160

160

and so, the first merge we'll do on the left side 161

161

will be merging 35 with minus 15. 162

162

So we're always merging the last split. 163

163

Okay, so let's look at the right array now. 164

164

So the start index is three. 165

165

The end is seven. 166

166

The midpoint will be five, 167

167

so elements three and four will go into the left array, 168

168

and elements five to six will go into the right array. 169

169

Now let's work on the left array, 170

170

the one that has seven and 55. 171

171

The midpoint will be four, 172

172

so we're gonna put element three to three into left 173

173

and four to four into right, 174

174

and we've now finished splitting the left array 175

175

on the right side. 176

176

So now we're gonna split the right array on the right side. 177

177

So the start index is five. 178

178

The end index is seven. 179

179

The midpoint is six. 180

180

So we're gonna put element five into the left array 181

181

and element six into the right array, 182

182

and we have now completed splitting the right array 183

183

into one-element arrays, 184

184

and once again, seven and 55 are both shaded 185

185

gold, yellow, brown, whatever you wanna, 186

186

however you wanna look at that. 187

187

They're shaded the same because they're sibling arrays. 188

188

They're gonna get merged together first, 189

189

and the same applies to one and minus 22. 190

190

So now we need to merge these arrays back together, 191

191

and remember, when we do the merge, we actually sort. 192

192

So every time we merge, the resulting array is sorted. 193

193

So as I mentioned, 35 and minus 15 194

194

are sibling left/right arrays, 195

195

so they're gonna get merged. 196

196

Seven and 55 are gonna get merged. 197

197

One and minus 22 are gonna get merged. 198

198

20 won't get merged right now 199

199

because it doesn't have a sibling at the moment. 200

200

So we started with our original array, 201

201

and then, we split that into a left array and a right array, 202

202

and then, that left array was split into left and right, 203

203

and that right array was split into left and right, 204

204

and then here, the right array 205

205

was split into two two-element arrays, 206

206

and then, they were each split into two one-element arrays, 207

207

and that's what we just went through in the slides. 208

208

Now because of the recursive nature of the implementation, 209

209

it's important to note that 210

210

we're going to handle the entire left side of the array 211

211

before we start working with the right side of the array 212

212

because you'll see from the implementation 213

213

that we call a method to partition the left side, 214

214

and then, we call a method to partition the right side, 215

215

but that method will call itself recursively, 216

216

and so, we'll call the method to partition the left side, 217

217

and then, it will call methods to partition 218

218

itself into left and right, 219

219

and this one will call 220

220

a method to partition itself into left and right, 221

221

and so, once we start down this path, 222

222

we go down the recursive rabbit hole, 223

223

and so, by the time the method called 224

224

to partition the left returns, 225

225

we'll have done all this work, 226

226

and the same goes for the right side. 227

227

So let's move on to the merging step now, 228

228

and you'll see that when we do the merging step, 229

229

we merge backwards, so we merge bottom up, 230

230

and we're gonna merge sibling arrays, 231

231

so we'll start by merging 35 with minus 15 232

232

and then seven with 55 an then one with minus 22, 233

233

and only after we've merged 35 and minus 15 234

234

back into a two-element sorted array 235

235

will we then merge 20 with the result, et cetera. 236

236

So we're gonna merge all these one-element arrays. 237

237

We always merge sibling left and right, 238

238

and each merged array will be sorted, 239

239

and as I said, 20 doesn't have a sibling, 240

240

so it's not gonna get merged on the first round. 241

241

So the way that the merging works 242

242

is we merge sibling left and right arrays, 243

243

and what we do is we create a temporary array 244

244

large enough to hold all the elements 245

245

in the arrays we're merging. 246

246

So on the first round, 247

247

our temporary arrays will be of length two 248

248

because we're going to be merging two one-element arrays, 249

249

and what we do is we set i 250

250

to the first index of the left array, 251

251

and j to the first index of the right array, 252

252

and when I say left and right array, 253

253

I mean the two arrays we're merging, 254

254

and then, we compare the value at the i position in left 255

255

to the value at the j position in the right array, 256

256

and if the value in the left array is smaller, 257

257

we copy that to the temporary array, 258

258

and we increment i by one. 259

259

If the value on the right array is smaller, 260

260

then we copy that to the temporary array 261

261

and increment j by one. 262

262

So essentially, what we're doing 263

263

is we're stepping through the left and right arrays, 264

264

and we're taking the smallest value 265

265

between the left and the right 266

266

and copying it into the temporary array, 267

267

and if we keep doing that, 268

268

that temporary array will contain the values 269

269

in sorted order. 270

270

So we're gonna repeat that until all the elements 271

271

in both arrays have been processed, 272

272

and, as I said, at that point, 273

273

the temporary array will contain the merged values 274

274

in sorted order, 275

275

and then, we have one final step to do. 276

276

Remember, we've been copying these values 277

277

into a temporary array, 278

278

so we then have to copy the sorted values 279

279

back into the original input array, 280

280

the one that we're sorting, at the correct positions, 281

281

and so, if the left array is at positions x to y 282

282

in the original array, 283

283

and the right array is at positions y plus one to z, 284

284

then after the copy, positions x to z 285

285

will be sorted in the original array. 286

286

So we're gonna overwrite what's there in the original array 287

287

with the sorted values. 288

288

So we're gonna start by merging the two siblings 289

289

on the left, 35 and minus 15. 290

290

So what we'll do is we'll create 291

291

a temporary two-element array. 292

292

i will be initialised to one 293

293

because that's the first index in the left array, 294

294

and j will be initialised to two 295

295

because that's the first index in the right array, 296

296

and then we compare array i to array j. 297

297

Minus 15 is smaller than 35. 298

298

There's a typo there, that should be 35, 299

299

and so, we copy minus 15 to the temporary array. 300

300

Then, we're gonna copy 35 to the temporary array, 301

301

and at this point, the temporary array 302

302

will be minus 15 and 35, 303

303

and we've now seen all of the elements 304

304

in the left array and right array that we're merging. 305

305

So at this point, we wanna copy the temporary array 306

306

back into positions one and two in the original array, 307

307

and so, at this point, minus 15 and 35 are sorted. 308

308

Now, they're not in sorted position in the array, 309

309

but the merged array is sorted, 310

310

and the two sibling arrays have now been merged. 311

311

So now, we're back to two arrays on the left-hand side. 312

312

We're back to 20, and we're back to minus 15 and 35. 313

313

So at this point, the left array contains 20, 314

314

and the right array contains minus 15 and 35. 315

315

So now we're gonna merge those two arrays 316

316

because 20 and minus 15 and 35 317

317

are sibling arrays now. 318

318

We originally got those two arrays 319

319

when we split the left array. 320

320

So we create a temporary array of length three. 321

321

i will be initialised to zero, 322

322

and j will be initialised to one, 323

323

and then, we compare array zero to array one. 324

324

Minus 15 is less than 20, 325

325

so it's gonna be copied to the temporary array, 326

326

and because we copied the value from the right array 327

327

into the temporary array, we increment j by one 328

328

because we've processed minus 15. 329

329

i is still zero because we haven't processed 20 yet. 330

330

So now we compare 20 to 35. 331

331

20 is smaller than 35, so it gets copied next, 332

332

and now, only 35 remains, and so, it's copied last, 333

333

and so, the temporary array consists of minus 15, 20 and 35, 334

334

and now, we copy that back into positions zero to two 335

335

in the original array, 336

336

and so, at this point, we have completed 337

337

merging the left sub-array, 338

338

and, as you can see, it's in sorted order. 339

339

So now, we're gonna repeat this process with the right 340

340

part of the array. 341

341

We have two sets of siblings, 342

342

seven and 55 and one and minus 22, 343

343

so we're gonna start by merging seven and 55. 344

344

So we're gonna create a temporary array of length two. 345

345

i will be initialised to three, 346

346

and j will be initialised to four. 347

347

We're gonna compare array i to array j. 348

348

Seven is smaller than 55, 349

349

so it gets copied into the temporary array first, 350

350

and then, 55 will get copied, 351

351

and then we copy the temp array 352

352

back to positions three and four, 353

353

and so, we've now merged the left array 354

354

of the right part of the original array, 355

355

and seven and 55 are in sorted order. 356

356

Now we repeat this process to merge one and minus 22. 357

357

The temporary array is gonna end up being minus 22 and one. 358

358

We're gonna copy that back into positions five and six, 359

359

and we're back to minus 22, 360

360

and the merged array is in sorted order. 361

361

It's minus 22 and one. 362

362

So now we have two arrays of length two, 363

363

and we need to merge those. 364

364

So we're gonna create a temporary array of length four. 365

365

i will be initialised to three and j to five. 366

366

Minus 22 is less than seven, 367

367

so we're gonna copy minus 22 to the temporary array, 368

368

and j will be incremented to six. 369

369

So then, we're gonna compare seven to one. 370

370

One is less than seven, 371

371

so one is gonna be copied to the temporary array, 372

372

and j will be incremented to seven. 373

373

Now, only elements in the left array are left, 374

374

and we know that they're sorted 375

375

because all the merged arrays are sorted, 376

376

and so, all we have to do at this point 377

377

is just copy the two elements from the left array 378

378

into the temporary array, and when we've done that, 379

379

the temporary array will be minus 22, one, seven, and 55, 380

380

and we just have to copy that 381

381

back into positions three to six, 382

382

and so, now we're back down to just two arrays, 383

383

a left array and a right array 384

384

that are both in sorted order, 385

385

and our final step is to merge these left and right arrays, 386

386

and so, we're gonna create a temporary array 387

387

that has enough room to hold seven elements. 388

388

We're gonna initialise i to zero and j to three. 389

389

Minus 22 is less than minus 15, 390

390

so we're gonna copy minus 22 to the temporary array, 391

391

and we're gonna increment j to four. 392

392

Minus 15 is less than one, 393

393

so we're gonna copy minus 15 to the temporary array, 394

394

and i is gonna get incremented to one. 395

395

One is less than 20, so we copy one to the temporary array, 396

396

and we increment j to five. 397

397

Seven is less than 20, 398

398

so we copy seven to the temporary array, 399

399

and we increment j to six. 400

400

20 is less than 55, so we copy 20 to the temporary array, 401

401

and we increment i to two, 402

402

and finally, 35 is less than 55, 403

403

so we copy 35 to the temporary array, 404

404

and we increment i to three, 405

405

and at this point, only 55 is left, 406

406

so we copy it to the temporary array, 407

407

and now we copy the temporary array 408

408

back into positions zero to six 409

409

because we've looked at all the elements, 410

410

and when we do that, the array is sorted. 411

411

It is quite a bit of work, 412

412

but because we're dividing and conquering, 413

413

we're splitting the array into two at each phase, 414

414

it actually performs better 415

415

than the algorithms we've seen so far. 416

416

So just to remind you of what we had 417

417

when we started the merging phase, 418

418

we had done all of the splitting, 419

419

and then, in the merging phase, 420

420

we went from the bottom back up. 421

421

So we merged 35 and minus 15 422

422

into a two-element sorted array of minus 15 and 35, 423

423

and we did the same thing with these two elements, 424

424

and the same thing with one and minus 22, 425

425

and then, at that point, these guys are now sibling arrays, 426

426

and so, we merged the left array with the right array, 427

427

and we got a sorted three-element array, 428

428

minus 15, 20, and 35, 429

429

and on this side, we had two two-element sibling array, 430

430

left and right. 431

431

We merged them into a sorted array, 432

432

and then, finally, we merged the original 433

433

left and right arrays we got from splitting the whole array 434

434

except this time, they're sorted 435

435

because we've undergone the merge step, 436

436

and so, we merged the sorted left array 437

437

with the sorted right array, 438

438

and our result from the merge is always a sorted array, 439

439

and so, we got our original array sorted. 440

440

So let's take a look at how this algorithm performs. 441

441

Well, first of all, as I said previously, 442

442

it's not an in-place algorithm. 443

443

The splitting phase is in-place, 444

444

but when we do the merging phase, 445

445

we use a temporary array to merge 446

446

each pair of sibling arrays. 447

447

Now this has a time complexity of O to the n log n, 448

448

and the log is to the base two, and why is that? 449

449

Well, we're repeatedly dividing the array in half 450

450

during the splitting phase, 451

451

and so, this is a logarithmic algorithm. 452

452

It's a stable sort algorithm 453

453

because when we do the merging, 454

454

we check whether the element in the right array 455

455

is greater than the element in the left array, 456

456

and if it isn't, if it's equal to it, 457

457

then the element in the left array will be the one 458

458

that's copied into the temporary array first, 459

459

and because of that, 460

460

the relative ordering of duplicate items will be preserved. 461

461

Now as I mentioned on the last slide, 462

462

the implementation I'm going to show you 463

463

has a couple of optimizations, 464

464

and I'll explain those 465

465

when we go through the implementation, 466

466

but it's still merge sort, 467

467

and it's still a logarithmic algorithm. 468

468

Now these days, memory is cheap and plentiful, 469

469

so the fact that it's not an in-place algorithm 470

470

shouldn't dissuade you from using it, 471

471

but if memory is an issue, then that's a consideration 472

472

because there's a lot of temporary array instances created, 473

473

and of course, the amount of memory you're going to need 474

474

is going to grow 475

475

as the number of items you're sorting grows. 476

476

As you'll see, the next sort algorithm we look at 477

477

also uses a divide and conquer philosophy 478

478

and is also a logarithmic algorithm, 479

479

but it's an in-place algorithm. 480

480

So we'll see that coming up in a couple of videos. 481

481

All right, so that's how merge sort works. 482

482

Let's implement it. 483

483

I'll see you in the next video.