Original subtitles

1 1

Alright, so now 2

2

we're going to implement merge sort, 3

3

and as I said in the slides, there is recursion involved, 4

4

so if you're having a problem understanding what's going on, 5

5

just go back and review the slides about merge sort 6

6

when we step through to sort by hand, 7

7

and you can also go back and review 8

8

the video on recursion. 9

9

Alright, so, I'm going to write two methods. 10

10

One called merge sort and this is 11

11

the merge sort implementation, 12

12

and it's the method that's going to call itself recursively. 13

13

And then I'm gonna write a second method called merge. 14

14

And that will be doing the merging step. 15

15

So let's get right to it. 16

16

So I'm gonna say public static void merge sort 17

17

and we're gonna pass the array that we wanna sort. 18

18

And we're gonna pass the start index 19

19

and an end index. 20

20

Okay, so the first thing we're gonna do here is, 21

21

for recursion, as I said, we need a breaking condition. 22

22

And this is going to be a recursive method, 23

23

so we need to know when to break out of the recursion 24

24

and we're gonna break out of the recursion 25

25

when this method is called with a one element array, 26

26

because when we have a one element array, 27

27

there's nothing to be done, by definition, 28

28

a one element array is sorted. 29

29

So we're going to say if and minus start, 30

30

is less than two, we just return. 31

31

And this will break the recursion, 32

32

so if we've been calling this method recursively, 33

33

the moment end minus start is less than two 34

34

meaning that we have a one element array, 35

35

we'll return and then the call to merge sort, 36

36

that's waiting for this call to return will be able 37

37

to continue executing, and then the call 38

38

that's waiting for that call to return 39

39

will be able to continue executing et cetera. 40

40

Like I said, you can go back and review the video 41

41

on recursion if you don't understand what I'm talking about. 42

42

Okay, so let's assume we don't have a one element array, 43

43

we have two or more elements, well then we have work to do. 44

44

And so the first thing we're going to do is partition 45

45

the array that we've been past, 46

46

now the array can be a sub array. 47

47

For example, on the first invocation 48

48

we're gonna get the entire array. 49

49

But on the second invocation of this, 50

50

we're just going to be getting this part. 51

51

This left array. 52

52

And so, in that case when we partition, 53

53

we're gonna be partitioning this array 54

54

just as we saw on the slides. 55

55

So what do we mean by partition, 56

56

well we basically just want to figure out 57

57

what the start and end indices are. 58

58

That's all we need to do in the partition phase, 59

59

because it's a logical partition, 60

60

we're not creating any new array instances. 61

61

And so let's do the partitioning, 62

62

so we'll say, int mid, 63

63

equals, and as we saw in the slides, 64

64

that will be start plus end, over two. 65

65

And so, for the first invocation, 66

66

start is gonna be zero, end is going to be seven, 67

67

because as I mentioned in the slides, 68

68

end is always one grader than the last valid index 69

69

of the partition that you want to sort, 70

70

and so we'll have zero plus seven over two, which is three. 71

71

And so at this point, hard to believe, 72

72

but we've partitioned the array, 73

73

we basically said that yeah, the mid point is three, 74

74

so we're gonna throw position zero, one and two 75

75

into the left array. 76

76

And we're gonna throw positions three, four, 77

77

five and six into the right array. 78

78

And now what do we wanna do? 79

79

We want to do a merge sort on the left partition. 80

80

So let's go ahead and do that. 81

81

So we'll say merge sort. 82

82

Input, it's always gonna be the same input array 83

83

'cause we're doing logical partitioning. 84

84

And then, the left array starts at position zero, 85

85

so it'll be the same start index. 86

86

And the end index for the left array will be mid. 87

87

Remember that in this implementation 88

88

the end index is always one greater 89

89

than the last valid index in the array. 90

90

I'm going to copy this, 91

91

and move it down here. 92

92

As a comment, so we can see it. 93

93

As we're working on this method. 94

94

And so, as I said in the first invocation, 95

95

we're gonna come in, end minus start, 96

96

seven minus zero is seven, so, 97

97

we definitely have more than one element in the partition 98

98

that we're working with. 99

99

Mid will be zero plus seven over two, 100

100

which is three. 101

101

And in this implementation we throw any extra elements 102

102

into the right partition. 103

103

And so we're gonna say, okay, so the left partition 104

104

is gonna consist of the indices from zero to two. 105

105

For the end position we always pass one greater. 106

106

And so that'll be mid, which is three. 107

107

So by passing start to zero end is three 108

108

we're saying we want position zero to two, 109

109

to go into the left partition. 110

110

And so we've handled the left partition now 111

111

because this is recursive, 112

112

when this call returns as we saw in the slides, 113

113

this entire array, left side, left sub array 114

114

will have been handled. 115

115

And so this call when we come in, 116

116

is gonna result in another call to merge sort, 117

117

another call to merge sort, until this guy has been 118

118

partitioned down to one element arrays 119

119

and then merged, and we'll get to that in a minute. 120

120

So by the time we come back, 121

121

these three elements will have been sorted. 122

122

So, the partition has been done, 123

123

the merge has been done and they're sorted 124

124

so tat this point, the left part of the array is sorted 125

125

and so we still need to handle the right part of the array. 126

126

So we'll call merge sort again with input, 127

127

this time, our start index will be mid, 128

128

and our end index will be end. 129

129

And so for the left array, we have a start index of zero 130

130

and an end index of three so we wanna handle 131

131

position zero to two. 132

132

And for the right part of the array, well, 133

133

we want these guys in the right part of the array, 134

134

so that's starting at position three, 135

135

position mid, and then we pass ending again, seven, 136

136

because we always pass one greater than the last valid index 137

137

in their partition, so that means indices three to six, 138

138

are in the right partition and by the time 139

139

this guy returns, this entire array will have been handled, 140

140

will have been partitioned down and sorted. 141

141

And so when we get to this point, when these two merge sort 142

142

calls complete, the elements in the first three positions 143

143

are in sorted order and the elements in the last four 144

144

positions are in sorted order and our final step, of course, 145

145

is to merge the left and right partitions. 146

146

And both of those partitions and now sorted, remember, 147

147

we always merge sorted partitions. 148

148

And so this is where we're gonna call our merge method. 149

149

And it's gonna take the input array, 150

150

the start index, the mid index and the end index. 151

151

And so because of recursion, when we come in, 152

152

with the full array, and then we're gonna call merge sort 153

153

with this partition, when we call merge sort 154

154

with this partition and it enters again, 155

155

it will call merge sort with this guy. 156

156

Remember that from the slides this guy, 157

157

the left array for this guy will be 20. 158

158

And then it will call merge sort with 35 and minus 15. 159

159

And that'll come back in and that's gonna split 160

160

these guys into two on element arrays. 161

161

And after that's been done, if we're working 162

162

with this array again, so after 20 has been handled here, 163

163

and 35 and minus 15 has been handled here, 164

164

then we'll merge those two arrays. 165

165

And then this call will return and at that point 166

166

the merge sort for the entire array 167

167

will be able to resume. 168

168

And then we'll handle the right side. 169

169

So as I said, if you're having a problem 170

170

understanding that we're going down 171

171

the recursion rabbit hole, each time we call this, 172

172

we're gonna completely process that, 173

173

or the left side, for the first invocation 174

174

will completely process that. 175

175

When we call this, we'll completely process the right side 176

176

and so by the time we hit this merge, 177

177

the left partition has been fully handled, 178

178

it's been partitioned, merged and so it's sorted 179

179

and the right side has been handled, 180

180

so it's been partitioned ad merged, so it's sorted. 181

181

And so, once we merge the left and right, 182

182

we have completely handled whatever partition 183

183

we called the method with. 184

184

And so when we call it with the entire array, 185

185

by the time this is returned and that's returned, 186

186

we're in a position to just merge the left and right, 187

187

and our array will be sorted. 188

188

So let's write the merge method. 189

189

So public static void merge. 190

190

And it takes an input array. 191

191

Start index, mid index, and end index. 192

192

Let me pull this up. 193

193

Okay, so I'm gonna copy this down again, 194

194

so I can refer to it, without having to scroll up and down. 195

195

Alright, so I said in the slides that the implementation 196

196

I'm going to show you has a couple of optimizations 197

197

and here's the first one. 198

198

So, we're gonna say if input mid minus one, 199

199

is less than or equal to input mid. 200

200

We're done. 201

201

We don't actually have to do any merging. 202

202

Now what the heck does this mean, 203

203

what is it doing? 204

204

Well, as we've said, we're always merging sorted arrays. 205

205

So, when we call merge the left partition 206

206

that we're merging is sorted. 207

207

And the right partition is sorted. 208

208

And we know that mid is the first element 209

209

in the right side and it's one greater 210

210

than the last element in the left side. 211

211

And so, input mid minus one, 212

212

is the last element in the left partition. 213

213

And input mid is the first element in the right partition. 214

214

Now, if the last element in the left partition 215

215

is less than or equal the first element 216

216

in the right partition that means all the elements 217

217

in the left partition are less than or equal 218

218

than the smallest element in the right partition, 219

219

because both of these guys are sorted. 220

220

And so, if the last element in the left partition 221

221

is, let's say 20, and the first element 222

222

in the right partition is 25, 223

223

then we know that all the elements in the right partition 224

224

are gonna be greater than or equal to all the elements 225

225

in the left partition, because these are sorted. 226

226

So if the last guy is 20, everything else in this array 227

227

is equal to 20 or less. 228

228

And if the first guy in the right array is 25, 229

229

then everything else in the right array is greater than 230

230

or equal to 25. 231

231

And so essentially we have the situation here that 232

232

if we were to go through the merge process for these guys, 233

233

we'd end up copying the entire left array 234

234

into the temporary array, 235

235

and then we copy the entire right array 236

236

into the temporary array, 'cause essentially, 237

237

because all the elements in the left array 238

238

are smaller than all the elements in the right array 239

239

to merge them, we just need to stick them together. 240

240

We just need to copy the left array 241

241

and then the right array. 242

242

But remember that after that, we would copy 243

243

the merged array back into the original array. 244

244

Into the positions that are already occupied 245

245

by these guys and what that means is, 246

246

we're not gonna change the original array in any way 247

247

'cause we're just gonna end up copying the elements back 248

248

in the same order they're already in. 249

249

And so for example for our array, 250

250

one of the partitions, as we saw in the slides, 251

251

is seven and 55. 252

252

And seven and 55 is going to be partitioned 253

253

into two arrays, right? 254

254

Seven, and 55, and so when we come in to this merge, 255

255

with the left array being seven, 256

256

and the right array being 55, 257

257

we're gonna compare input mid minus one, 258

258

which will give us seven, with input mid, 259

259

which will give us 55. 260

260

Now because 55 is greater than seven, 261

261

what we would do is copy seven to the temporary array, 262

262

and then we copy 55 to the temporary array, 263

263

so we end up with seven and 55, we end up with them 264

264

in the exact same order they're already in. 265

265

And then we're gonna copy them back 266

266

into the two positions they're currently occupied. 267

267

And so basically we're doing needless work. 268

268

And so, what this is saying is, 269

269

if everything in the left array is smaller 270

270

than everything in the right array, 271

271

then the merged array, is just going to be 272

272

the left array followed by the right array. 273

273

And so, none of the positions of the elements 274

274

are going to change. 275

275

And so when we copy back the temp array, 276

276

we're gonna be copying the same elements 277

277

back to the same positions, 278

278

so we don't actually have to do anything. 279

279

When we get to seven, merging seven and 55, 280

280

we don't have to do anything, they're already in 281

281

their correct sorted positions, relative to each other. 282

282

And so that's what this optimization is doing. 283

283

It's saying, it's stopping us from going ahead 284

284

and merging our left and right array, 285

285

when we don't have to do that, 286

286

because the result of the merge is going to equal 287

287

what we already have in the input array, okay. 288

288

And this works because we know at this point 289

289

that both the left and right partitions are sorted. 290

290

If they weren't sorted, we couldn't do this check. 291

291

Alright, so if that's not the case, 292

292

it means that we have some elements in the left array 293

293

that are greater, than some of the elements 294

294

in the right array, so we have merging to do. 295

295

'Cause some of the positions of the elements 296

296

are going to change, when we do the merge. 297

297

And so we're going to initialise, I to start, 298

298

just like we did in the slides. 299

299

We're gonna initialise J to mid, 300

300

and we're gonna have this new temp index, 301

301

that we're gonna initialise to zero. 302

302

And this is going to keep track of where we are 303

303

in the temporary array, when we're doing the copy. 304

304

So now we're gonna create our temporary array, 305

305

so we'll say int temp. 306

306

Int temp equals new int and the lengths will be 307

307

end minus start, we need this to be large enough 308

308

to hold the number of elements in the left 309

309

and right partitions, and so, if we're doing 310

310

the whole array, end will be seven and start will be zero 311

311

so we'll end up with a integer array of seven 312

312

and that's what we want. 313

313

And then what we're going to do, is, 314

314

we're going to step through the left and right arrays 315

315

and we're gonna compare whatever is at index I, 316

316

in the left array, with whatever is at index J, 317

317

in the right array. 318

318

And we're going to write the smaller of the two 319

319

into the current position in temp. 320

320

Which we're keeping track of with temp index, 321

321

so we're gonna say, while I is less than mid, 322

322

and J is less than end. 323

323

And we're gonna say temp. 324

324

Temp index plus plus, equals, while if input I, 325

325

is less than or equal to input J, 326

326

then we wanna write whatever is at I, 327

327

into the temporary array, 328

328

because it's the smaller of the two. 329

329

And so we're gonna say. 330

330

And so we're going to assign input I plus plus, 331

331

to temp, temp index otherwise, 332

332

we're gonna assign input J plus plus, to temp. 333

333

And so to review what's going on here, 334

334

when I equals mid, we'll have finished 335

335

traversing the left array. 336

336

So as soon as we've finished traversing the left array 337

337

we wanna drop out or, as soon as we finish traversing 338

338

the right array, we wanna drop out. 339

339

So once we have finished completely traversing 340

340

either the left or the right array, 341

341

we're gonna drop out of the loop, 342

342

and don't worry, we'll handle any 343

343

left over elements in a minute. 344

344

So assuming that hasn't happened, 345

345

we're going to compare the current element 346

346

in the left partition which we're keeping track of 347

347

which element that is with I, 348

348

we're gonna compare that with the current element 349

349

in the right partition, which we're keeping 350

350

track of with J, and we're gonna write the smaller 351

351

of the two to the temporary array. 352

352

Now because merge sort is stable, we have the equals here. 353

353

And so, if the element in the left array, 354

354

is equal to the element in the right array 355

355

it will be written first, and that's how we preserve 356

356

the relative ordering of duplicate items. 357

357

If we didn't have this equals here, 358

358

this would become unstable. 359

359

And so if input I is less than or equal to input J, 360

360

we're gonna assign input I to the current position 361

361

in temp and then we're gonna increment the temp index 362

362

and we're gonna increment I. 363

363

'Cause now we wanna move on to the next element 364

364

in the left partition. 365

365

But if input J is the smaller of the two, 366

366

so that means that input J, the element 367

367

in the right partition is less than the element 368

368

in the left partition, then we'll write the element 369

369

in the right partition. 370

370

And then of course we'll increment J, 371

371

we'll increment the temp index. 372

372

So we're doing what you saw in the slides, 373

373

we're traversing through the left and right partitions 374

374

and on each test we write the smaller element 375

375

between the left and the right into the temp array 376

376

and by always the always writing the smaller element 377

377

at the end the temp array will contain elements 378

378

from the left and right partitions in sorted order 379

379

and we'll have sorted, so we'll have merged 380

380

the two partitions and the resulting partition 381

381

will be sorted. 382

382

Now because we're dropping out of the loop, 383

383

when we've completely traversed the one of the arrays, 384

384

the other array or partition, sub array, 385

385

however you wanna call it, 386

386

the other one will have some elements left over 387

387

that we have not copied in to temp 388

388

and so we have to handle that now. 389

389

And this just going to be the second optimization. 390

390

This is going to be handling the remaining elements 391

391

in the array that we have in traverse. 392

392

Now the optimization is that if we have elements 393

393

remaining in the left partition, 394

394

we have to copy them into the temp array. 395

395

But, if we have elements remaining in the right partition 396

396

we don't have to do anything. 397

397

And you might be thinking, well why not? 398

398

Its kind of the same situation that we had 399

399

with the first optimization. 400

400

When we're copying the elements back, 401

401

we're copying them back into the positions 402

402

that are covered by the left and right partitions, so. 403

403

Okay, so let me do an example on the fly here. 404

404

So let's say, we're merging these two arrays. 405

405

So we're merging 32 and 34 in on the right side, 406

406

we have 33 and 36, let's say. 407

407

So this is the left side, this is the right side, 408

408

they're in sorted order, each array, 409

409

because we're always merging sorted partitions. 410

410

So when we do the merge, 411

411

we compare 32 to 33, well 32 is the smaller of the two, 412

412

so we'd write 32, and then we'll compare 34 to 33, 413

413

well, 33 is the smaller of the two, 414

414

so we'll write 33, we'll compare 34 to 36, 415

415

34 is the smaller, so we'll write 34 and at this point 416

416

we would drop out of the loop, 417

417

because we've completely finished traversing the left array. 418

418

We haven't handled 36, 36 isn't here, 419

419

but we don't need to, because remember, we're gonna copy, 420

420

temporary array back into the four positions 421

421

that these guys currently occupy. 422

422

And if you'll notice, if we were to add 36 in here, 423

423

then when we copy the temporary array 424

424

back into the input array, we'd be overwriting 36 425

425

with 36, so once again, we'd be doing needless work. 426

426

If we have elements left over in the right array, 427

427

that means that all of the elements 428

428

that are left over in the right array will be greater, 429

429

than everything that's already been copied. 430

430

Because remember, we're always copying the smallest 431

431

of the elements, so if we have elements left over 432

432

in the right, we know that they're greater 433

433

than everything else, that's why 434

434

they haven't been copied yet. 435

435

And so, if we've completely seen the left array, 436

436

anything left over in the right array, is greater 437

437

than everything we've already copied. 438

438

And so, whatever's left over, its position 439

439

in the input array, is not going to change, 440

440

as a result of the merge. 441

441

And so if we were to take any left over elements 442

442

in the right array, copy them into temp 443

443

and then copy them back, we're doing needless work again, 444

444

because you know, we're copying elements 445

445

back into the same positions they occupied before. 446

446

And so, we don't have to worry about handling 447

447

any left over elements in the right array. 448

448

Their positions in the input array will not change 449

449

as a result of the merge, but that's not true 450

450

of the left array. 451

451

If we have elements left over in the left array, 452

452

then those elements are greater than everything 453

453

we're already written and so, obviously 454

454

we need to write those, because their positions 455

455

are going to change, let me see if I can come up 456

456

with an example of that. 457

457

I'll put the 36 here, and I'll put 34 here I guess. 458

458

And so let's do it again. 459

459

So we're gonna write 32 and then we're gonna write 33, 460

460

and then we're gonna write 34. 461

461

And at this point, we have finished traversing 462

462

the right array, and you'll see that we have 36 left over, 463

463

well we have to handle that 464

464

because its position is gonna change. 465

465

It's going to go from coming second, 466

466

when we're looking at these four numbers, 467

467

to coming fourth. 468

468

And so when we copy the temporary array 469

469

back tot he original array, the input array, 470

470

the position of 36 will have to change. 471

471

And so once again, if it's elements in the left array 472

472

that are left over, we know that those elements 473

473

are greater than everything that's already 474

474

been written and so basically all those elements 475

475

need to jump over whatever is in the right array. 476

476

So their positions are going to change. 477

477

So if there are elements left over in the left array 478

478

we have to handle them. 479

479

We have to copy them into the temp array. 480

480

But if there are elements left over 481

481

in the right array, we don't have to. 482

482

Because their positions in the original array 483

483

aren't going to change, and so, 484

484

we'd be doing needless work, 485

485

if we copied them to temp and copied them back. 486

486

Now, when we do the copy, we copy the remaining 487

487

left elements in the left array over. 488

488

We're not actually gonna copy them into temp. 489

489

Because as I just explained, basically, 490

490

they'll jump over all of the elements 491

491

that we've copied so far and so we can just do that copy 492

492

within the input array. 493

493

We know the positions we need to copy to. 494

494

And so we're gonna use system dot array copy. 495

495

The first parameter is the source array 496

496

and that'll be our input array, 497

497

and then we're gonna start the copy at position I, 498

498

because that will be, if there are left over elements 499

499

in the left array, this is the first index 500

500

of the first element that we still haven't handled. 501

501

And then out destination array will be the input array 502

502

and we're gonna copy to start plus temp index. 503

503

This is our destination index 504

504

and temp index has basically counted 505

505

how many elements we've handled. 506

506

And so the destination position for any elements 507

507

in the left array that are gonna basically jump over 508

508

all of the elements in the temporary array 509

509

is star plus temp index. 510

510

So if we're merging two two element arrays 511

511

and we've copied three elements into the temporary array 512

512

and we have that one left over element 513

513

in the left array, the left partition 514

514

that we haven't handled, well, 515

515

we'll add three to the start index 516

516

and so it'll be copied into the original input array 517

517

after the elements that we're gonna copy in 518

518

from the temp array. 519

519

So we don't actually copy and left over elements 520

520

in the left partition into the temp array. 521

521

We just copy them directly into where they'd end up, 522

522

in the input array. 523

523

And the lengths that we're gonna write is mid minus I. 524

524

This tells us the number of elements 525

525

that we didn't copy over into the temp array 526

526

from the left partition. 527

527

Now if we completely traversed the left array, 528

528

this will end up being zero, 529

529

and so we won't actually do a copy here, okay. 530

530

And if we didn't completely traversed the right array, 531

531

once again, this array copy won't do anything 532

532

because this isn't paying any attention to J, 533

533

it's just handling the left array. 534

534

So if there are no leftover elements in the left array 535

535

this won't do anything, if there are 536

536

left over elements in the left array, 537

537

this will copy them directly 538

538

from one location in the input array, 539

539

to another location in the input array, 540

540

it'll essentially jump over the elements we're gonna copy 541

541

from the temp array and write any remaining elements 542

542

in the left array. 543

543

And so our final step is to copy over the temp array. 544

544

So we're gonna say system dot array copy. 545

545

Our source array will be the temp array. 546

546

We're gonna start at zero, 'cause we wanna copy 547

547

from the beginning, the target will be the input array. 548

548

We're gonna copy starting at the start, 549

549

because remember, we're going to replace 550

550

when we do the merge we're handling position 551

551

start to end in the input array, 552

552

and so we're gonna start at start. 553

553

And the length we're gonna copy is temp index. 554

554

So we're only going to copy the number of elements 555

555

that we actually copied into the temp array. 556

556

We're not gonna copy the entire temp array. 557

557

And so, in this first array copy, here, 558

558

we're copying here up to temp index 559

559

and then here, if there are any left over elements 560

560

in the left array, we're starting at start plus temp index 561

561

and that's it. 562

562

That's our merge sort. 563

563

So let's call this, after all of that, let's hope this works 564

564

so we'll call merge sort. 565

565

We're gonna call it with our int array, 566

566

our start will be zero, and our end will be 567

567

int array dot length. 568

568

Let's give this a whirl. 569

569

And there we go, minus twenty two, minus fifteen, 570

570

one, seven, twenty, thirty five and fifty five. 571

571

Now, I think probably the most difficult part 572

572

to understand here, apart from how the recursion 573

573

is working, but you can review the recursion slides, 574

574

is perhaps what's going on here. 575

575

I think the key thing to understand here is 576

576

when we're merging a partition, 577

577

we're gonna copy the merged values 578

578

back into those same positions. 579

579

And so, the optimization down here, is, 580

580

if the greater values are already towards the right, 581

581

so they're already in the, at the end 582

582

of the right partition, their positions aren't gonna change 583

583

so there's no need to do the extra work 584

584

of copying them to the temp array 585

585

and copying them back. 586

586

And then if we have left over elements 587

587

in the left array, instead of copying 588

588

the left overs, let's say 55 would be left over here, 589

589

if we were to merge these two arrays, seven and 55 590

590

in one and minus 22, 55 is gonna get left here. 591

591

Because it's greater, so, we'll end up writing 592

592

minus 22, one and seven, to the temp array 593

593

and then 55 will be left over, 594

594

well instead of copying 55, to the end 595

595

of the temporary array, we take it, 596

596

and we directly copy it here. 597

597

'Cause we know that's where it's gonna end up. 598

598

And so that's what this line is doing here. 599

599

It's saying start with the input array, 600

600

start at I and I would be equal to the position of 55, 601

601

and then add start in temp index so we'd add three 602

602

to the start index, 'cause we've handled three elements, 603

603

so our start index would be here, 604

604

so we're gonna go one, two, three. 605

605

And that's where we're gonna copy 55 to. 606

606

And at that point, mid minus I would give us one. 607

607

And so we'd just copy that one element. 608

608

And so instead of copying 55 to the temp array 609

609

and then copying it back in, as we copy the temp array 610

610

in this step here, we just take 55 611

611

and we just plop it right in there. 612

612

And then on the second array copy, 613

613

we copy the temporary array. 614

614

So we'd copy minus 22, one and seven. 615

615

And 55 would already be sitting here, so, 616

616

you've seen me go through algorithms 617

617

or implementations on slides 618

618

going through code by hand is a fantastic way 619

619

to learn what the code is doing 620

620

and so if you're confused by any of this, 621

621

go through a couple of iterations using pen and paper. 622

622

Normally you don't have to do through the entire sorting 623

623

of the array just doing one of two calls will give you 624

624

a feel for what the implementation is doing. 625

625

And keep in mind that this is recursive 626

626

and so, if you're having trouble understanding 627

627

what this is doing, review the slides on recursion. 628

628

But that's merge sort. 629

629

It's doing a lot of work, it looks deceptively simple 630

630

but as I said in the recursion video, 631

631

three lines of code, of two lines of code, 632

632

when you're dealing with recursion can deal 633

633

to hundreds of calls, so there can be a lot 634

634

going on under the covers. 635

635

Alright, so let's move on now to the second algorithm 636

636

that uses divide and conquer, 637

637

I'll see you in the next video.