1
00:00:00,420 --> 00:00:05,970
‫So in this video, we're going to talk high level about how Merge sort works.

2
00:00:05,970 --> 00:00:08,910
‫And then in the next video, we'll code it.

3
00:00:09,330 --> 00:00:14,430
‫So I'm going to bring up this array and I've included the indexes.

4
00:00:14,700 --> 00:00:18,900
‫So merge sort is going to take this array and cut it in half.

5
00:00:19,140 --> 00:00:24,930
‫And the way it's going to do that is just by taking a smaller range of the array.

6
00:00:25,200 --> 00:00:28,590
‫But we are still dealing with the original array.

7
00:00:28,590 --> 00:00:35,010
‫It's just a smaller range of indexes, and then we'll do that on the other side as well.

8
00:00:35,130 --> 00:00:40,200
‫So then we'll take these and break them in half and then we'll take each of these and break them in

9
00:00:40,200 --> 00:00:41,850
‫half as well.

10
00:00:42,210 --> 00:00:48,360
‫So Merge Sort is going to take an array and cut it in half and then take the sub arrays and break those

11
00:00:48,360 --> 00:00:49,190
‫in half.

12
00:00:49,200 --> 00:00:56,880
‫And it will continue doing that until those sub arrays each have one item and then finally merge sort

13
00:00:56,880 --> 00:01:04,050
‫is going to call the merge helper function to take two items and sort them.

14
00:01:04,320 --> 00:01:07,650
‫And we'll do that with these items as well.

15
00:01:07,830 --> 00:01:15,570
‫And now, because these are all sorted arrays, we can take two of these arrays and combine them and

16
00:01:15,570 --> 00:01:17,940
‫the same thing with these two.

17
00:01:18,060 --> 00:01:26,070
‫And then we'll call merge on these two sorted sub arrays and combine them into one sorted array.

18
00:01:26,610 --> 00:01:33,510
‫So merge sort breaks arrays in half and it's going to do this recursively.

19
00:01:33,510 --> 00:01:36,450
‫And there are two requirements for recursion.

20
00:01:36,870 --> 00:01:43,440
‫First, you're doing the same thing over and over, and each time we're just breaking arrays in half.

21
00:01:43,440 --> 00:01:45,510
‫So it fits that requirement.

22
00:01:45,840 --> 00:01:49,680
‫But also you have to be making the problem smaller.

23
00:01:50,040 --> 00:01:56,670
‫And we're doing that by making the sub arrays smaller and smaller, and you continue making those smaller

24
00:01:56,670 --> 00:02:02,460
‫until you reach your base case, which is when the subquery size is one.

25
00:02:02,850 --> 00:02:10,500
‫And then finally with merge sort once we reach this base case is recall the merge helper function to

26
00:02:10,500 --> 00:02:13,170
‫put the sub arrays back together.

27
00:02:13,680 --> 00:02:18,330
‫So we will code and walk through merge sort in the next video.

28
00:02:18,660 --> 00:02:23,070
‫But for now, that is our introduction to merge sort.