1
00:00:00,450 --> 00:00:05,730
‫So now we're going to do the second video for writing our merge code.

2
00:00:06,120 --> 00:00:13,800
‫So I'm going to bring up this array that we saw in the last video with the two sorted sub arrays, and

3
00:00:13,800 --> 00:00:16,170
‫I'm going to shrink it down to the bottom.

4
00:00:16,710 --> 00:00:23,880
‫So in the last video, we created a new array called Left Array that had the values of the left sub

5
00:00:23,880 --> 00:00:24,510
‫array.

6
00:00:24,810 --> 00:00:31,680
‫And then we created another array called right array with the items from the right sub array.

7
00:00:31,980 --> 00:00:38,580
‫And because all of the values in the original array are going to be overwritten, I'm going to color

8
00:00:38,580 --> 00:00:40,890
‫the original array gray.

9
00:00:41,280 --> 00:00:48,450
‫So we got to this point in the last video with this code, and I want to emphasize that all of the code

10
00:00:48,450 --> 00:00:53,370
‫that we're writing in this video is just adding to this function.

11
00:00:53,970 --> 00:00:57,080
‫So I'm going to bring in the first additional line here.

12
00:00:57,090 --> 00:01:05,290
‫We'll set index to be equal to left index and left index as the first item in that array.

13
00:01:05,310 --> 00:01:12,500
‫So index will point to that and then we'll set I to be equal to zero.

14
00:01:12,510 --> 00:01:15,540
‫That will keep track of where we are in this array.

15
00:01:16,020 --> 00:01:22,230
‫J will also be set equal to zero and that will keep track of where we are in this array.

16
00:01:22,890 --> 00:01:24,960
‫So we'll bring in this wild loop.

17
00:01:24,960 --> 00:01:31,260
‫And this wild loop will run until one of the two arrays on the bottom is empty.

18
00:01:31,710 --> 00:01:38,820
‫And then inside of this wild loop, we'll check to see if left array at the index of AI is less than

19
00:01:38,820 --> 00:01:42,780
‫or equal to right array at the index of J.

20
00:01:43,290 --> 00:01:47,790
‫So I'm going to highlight the two items on the bottom that we're comparing.

21
00:01:48,090 --> 00:01:53,790
‫And in this iteration of the wild loop, the conditional in this if statement will be true.

22
00:01:54,210 --> 00:02:03,000
‫So then what we'll do is say array at index is equal to left index at the index of I and that just moves

23
00:02:03,000 --> 00:02:04,530
‫this up here.

24
00:02:04,800 --> 00:02:08,820
‫But now we need to move a couple of those arrows forward.

25
00:02:08,850 --> 00:02:17,610
‫First we'll say index plus plus and that moves that index arrow over one and then we'll say I plus plus.

26
00:02:17,610 --> 00:02:21,030
‫And that does the same thing for the I arrow.

27
00:02:21,540 --> 00:02:23,280
‫So we're running out of room here.

28
00:02:23,280 --> 00:02:25,800
‫So I'm going to move the wild loop up.

29
00:02:26,130 --> 00:02:32,940
‫And in the next iteration of this wild loop, when we compare the items in the left and right array,

30
00:02:32,970 --> 00:02:38,100
‫now it's the item in the right array that is less than so.

31
00:02:38,100 --> 00:02:41,880
‫Now the conditional in this if statement is going to be false.

32
00:02:41,880 --> 00:02:51,540
‫So now we'll say else, and now we'll set array at index to be equal to right array at the index of

33
00:02:51,540 --> 00:02:53,820
‫J like this.

34
00:02:54,240 --> 00:03:00,180
‫And just like we had in the if statement, we're going to have to iterate, index and move that over

35
00:03:00,450 --> 00:03:02,640
‫and then we'll have to move J over as well.

36
00:03:02,640 --> 00:03:06,300
‫We'll say J plus plus and that moves that over.

37
00:03:06,690 --> 00:03:09,660
‫So now let's run through this wild loop to the end.

38
00:03:09,660 --> 00:03:14,700
‫We move up three, four, five and six.

39
00:03:14,970 --> 00:03:20,700
‫But now, because the right array is empty, it breaks us out of this wild loop.

40
00:03:21,120 --> 00:03:27,480
‫So I'm going to remove this and we'll need a separate while loop to finish looping through the left

41
00:03:27,480 --> 00:03:28,290
‫array.

42
00:03:28,930 --> 00:03:36,370
‫So we'll do that like this and we'll just set a ray index to be equal to left a ray at the index of

43
00:03:36,370 --> 00:03:38,920
‫AI and that moves that up.

44
00:03:39,310 --> 00:03:47,530
‫And then we need to iterate index and that moves that arrow over and do the same thing for AI and that

45
00:03:47,530 --> 00:03:54,790
‫moves that over and then we'll run through this wild loop one more time and that copies that up to the

46
00:03:54,790 --> 00:03:56,320
‫original array.

47
00:03:56,920 --> 00:04:01,450
‫So in this case, we had items that were still left and the left array.

48
00:04:01,720 --> 00:04:05,830
‫It could work out that we have items left and the right array.

49
00:04:06,070 --> 00:04:12,670
‫So we'll create an almost identical while loop to deal with that situation just like this.

50
00:04:13,240 --> 00:04:18,520
‫And this will deal with a situation where we still have items left and the right array.

51
00:04:19,030 --> 00:04:23,110
‫Now let's bring in the rest of the code that we wrote in this video.

52
00:04:23,290 --> 00:04:30,010
‫And remember, this is all being added to the merge function that we started writing and the last video.

53
00:04:30,490 --> 00:04:35,740
‫So now let's flip over to VS Code and look at all of the code together.

54
00:04:36,920 --> 00:04:44,720
‫So here is the code that we wrote in the last video, and then I'll scroll up and in this video we created

55
00:04:44,720 --> 00:04:52,430
‫these three variables and this is the wild loop that runs until one of the two arrays, left or right,

56
00:04:52,430 --> 00:04:53,690
‫becomes empty.

57
00:04:54,170 --> 00:04:55,760
‫And I'll scroll up again.

58
00:04:56,360 --> 00:05:04,370
‫And then once one of the two arrays is empty, will run one of these two wild loops to finish iterating

59
00:05:04,370 --> 00:05:06,770
‫through the remaining items.

60
00:05:07,220 --> 00:05:09,440
‫So let's scroll up one more time.

61
00:05:09,620 --> 00:05:18,650
‫And then in our main function we have our array that contains a sorted left sub array and a sorted right

62
00:05:18,650 --> 00:05:26,490
‫summary, and with this line will calculate the size of the array and the left index will be zero and

63
00:05:26,510 --> 00:05:30,740
‫we'll use the size to calculate the right and mid index.

64
00:05:30,980 --> 00:05:37,220
‫And with this line we'll run merge on that array with left, mid and right index.

65
00:05:37,370 --> 00:05:40,820
‫And then with this four loop, we'll print that out.

66
00:05:41,120 --> 00:05:42,560
‫So I'll run this.

67
00:05:43,290 --> 00:05:48,090
‫And this has returned a sorted array one through eight.

68
00:05:48,720 --> 00:05:52,530
‫And that is our function for merge.