1
00:00:06,330 --> 00:00:14,160
In the previous lecture, we did an overview of what Merge sort is and how Merge sort works.

2
00:00:15,060 --> 00:00:20,850
And now that we have a good understanding of how Merge sort works, we can take that knowledge and begin

3
00:00:20,850 --> 00:00:23,340
implementing in our own solution.

4
00:00:24,420 --> 00:00:25,800
To that algorithm.

5
00:00:26,670 --> 00:00:33,420
So the first thing that I want to do is set up our logic that we're going to execute in main.

6
00:00:34,020 --> 00:00:35,640
So we'll create our VEC.

7
00:00:38,490 --> 00:00:43,050
And again, I want to use the same values that we used in the previous lecture.

8
00:00:43,050 --> 00:00:47,280
So four, seven, three, five, one and two.

9
00:00:48,390 --> 00:01:01,350
And then I want to call Merge sort and I want to pass in our VEC and then I want to print out the results

10
00:01:01,350 --> 00:01:02,730
of the sorted vector.

11
00:01:02,730 --> 00:01:05,760
That way we can confirm our work.

12
00:01:08,680 --> 00:01:12,580
So now we can come up here and we can begin implementing in our function.

13
00:01:12,580 --> 00:01:19,450
So we have merge sort and we're going to have an array and it's going to be a mutable and to mix it

14
00:01:19,450 --> 00:01:20,440
up a little bit.

15
00:01:20,530 --> 00:01:29,710
I want to do a slice and a slice and we can use an array slice because we technically don't need to

16
00:01:29,710 --> 00:01:31,750
own the data being passed in.

17
00:01:32,410 --> 00:01:39,610
We're just wanting to point to the block of memory that it is in, which is what this array slice does.

18
00:01:39,910 --> 00:01:47,590
So this allows for safe and efficient access to that memory block without having to copy the data.

19
00:01:49,270 --> 00:01:54,690
So at the end, I would like to return a vector.

20
00:01:54,700 --> 00:01:57,460
That way we can view our results.

21
00:01:57,550 --> 00:01:59,650
Once we execute our code.

22
00:02:00,130 --> 00:02:06,310
So inside a merge, we want to have a base case and we want to make sure the length of our array that's

23
00:02:06,310 --> 00:02:08,200
being passed in is greater than one.

24
00:02:09,310 --> 00:02:11,710
That way that there's actually some work to be done.

25
00:02:11,710 --> 00:02:15,610
Otherwise the array has one element and it is already sorted.

26
00:02:16,420 --> 00:02:22,240
So we need to get our midpoint and for us to get our midpoint, we can just simply take the array length

27
00:02:22,240 --> 00:02:23,850
and divide it by two.

28
00:02:23,860 --> 00:02:27,490
And that is going to give us our midway point in our array.

29
00:02:27,850 --> 00:02:38,560
And as I noted in the previous lecture, Merge sort is a recursive algorithm, which is why we went

30
00:02:38,560 --> 00:02:41,830
over recursion in the previous section.

31
00:02:42,700 --> 00:02:49,330
So as you know, with recursion and order for it to be recursive, you have to call the calling function

32
00:02:49,330 --> 00:02:50,860
from inside itself.

33
00:02:51,220 --> 00:02:53,410
So we are going to call our merge sort here.

34
00:02:53,560 --> 00:03:00,640
And what we're going to do is we're going to call it on the array from the beginning of the array to

35
00:03:00,640 --> 00:03:02,080
the midpoint.

36
00:03:02,470 --> 00:03:06,780
So this is going to be the left half of the array.

37
00:03:06,790 --> 00:03:14,260
So naturally, we need to call it on the right, half of the array.

38
00:03:15,250 --> 00:03:17,140
So we'll go from mid

39
00:03:20,080 --> 00:03:20,980
onwards.

40
00:03:21,910 --> 00:03:24,520
So this is the right half of the array.

41
00:03:25,060 --> 00:03:32,710
So now and just to get rid of all these errors, we're going to return our array as a vector.

42
00:03:34,120 --> 00:03:41,890
So now that we are actually doing the divide and conquer piece, remember once we're done with the recursive

43
00:03:41,890 --> 00:03:50,380
part and our stack begins to unwind, we need to merge all the elements back together in the correct

44
00:03:50,380 --> 00:03:51,060
order.

45
00:03:51,070 --> 00:03:57,550
So for us to do this, we're going to need an another function and I'm going to call it merge and we're

46
00:03:57,550 --> 00:04:01,180
going to pass in our array and also the midpoint.

47
00:04:02,110 --> 00:04:12,220
So Merge is going to be a helping function, helping function for us that's going to take our sorted

48
00:04:12,520 --> 00:04:20,800
or take our divided arrays and then after they're sorted and merge them back together into one array

49
00:04:20,800 --> 00:04:21,520
for us.

50
00:04:21,940 --> 00:04:26,680
So we're going to have array that's being passed in.

51
00:04:26,860 --> 00:04:32,680
And again, this is going to be a mutable slice, array, slice.

52
00:04:33,310 --> 00:04:38,140
And then we know that we're bringing in our mid variable as well.

53
00:04:38,200 --> 00:04:41,320
And this is going to be a type you size.

54
00:04:43,690 --> 00:04:51,040
So let's get the left half of the array that we passed in so that we can divide it even further.

55
00:04:52,330 --> 00:04:53,260
And.

56
00:04:54,450 --> 00:04:57,720
That is going to be from the beginning to the mid.

57
00:04:58,730 --> 00:05:01,400
We're gonna turn this into a vector.

58
00:05:03,020 --> 00:05:11,990
So again, so this is left half to middle, and then we're going to say, right, it's going to go from

59
00:05:11,990 --> 00:05:12,710
the mid.

60
00:05:15,610 --> 00:05:16,610
Onwards.

61
00:05:16,630 --> 00:05:24,010
So this is the right from excuse me, middle to the right half.

62
00:05:25,850 --> 00:05:34,250
They we're going to create two variables here called L four left and R four right.

63
00:05:34,850 --> 00:05:37,520
And these are going to be pretty important for us.

64
00:05:37,910 --> 00:05:40,370
So we'll see what they're going to do in a second.

65
00:05:40,790 --> 00:05:42,910
So now we're going to have a four loop.

66
00:05:42,920 --> 00:05:50,960
This way we can begin merging our elements back in and the assort in the sorted order.

67
00:05:51,620 --> 00:06:05,180
So we have for each value in the array if are are so this are here if R is equal to the right vector

68
00:06:05,180 --> 00:06:05,990
length.

69
00:06:08,650 --> 00:06:26,980
Or if our ll variable is less than lef dot links and left of l is less than right of R.

70
00:06:28,900 --> 00:06:30,600
So what are we doing here?

71
00:06:30,610 --> 00:06:37,390
So this is obviously a pretty long if check where it is an or statement.

72
00:06:37,390 --> 00:06:44,680
So remember that means either this side has to be true or all of this side has to be true.

73
00:06:46,170 --> 00:06:57,030
So if we are executing code in this block, so inside of this if statement, then that means R equals

74
00:06:58,890 --> 00:07:01,650
the length of this vector.

75
00:07:03,210 --> 00:07:04,110
Or.

76
00:07:07,070 --> 00:07:14,930
The LL variable here is less than the left vector length and left.

77
00:07:15,990 --> 00:07:20,640
This index is less than right of the right index.

78
00:07:20,910 --> 00:07:26,760
So we're doing a lot of checking based on where our indexes are at this level.

79
00:07:27,630 --> 00:07:33,030
So that would insinuate that we're going to need to update our indexes appropriately.

80
00:07:33,090 --> 00:07:38,910
So what we want to do is we want to reference the valve variable and here that way we can get the raw

81
00:07:38,910 --> 00:07:42,030
data in there and not some memory address.

82
00:07:42,840 --> 00:07:49,290
And we want to check if that vow is equal to left at index position L.

83
00:07:51,420 --> 00:07:54,840
And then we want to increment

84
00:07:57,540 --> 00:08:01,920
it by one else, we're going to do the same thing.

85
00:08:01,920 --> 00:08:03,930
But this time for ah, so we want to check it.

86
00:08:03,930 --> 00:08:08,070
The vowel is equal to right of our.

87
00:08:10,730 --> 00:08:12,240
And we want to increment it by one.

88
00:08:12,260 --> 00:08:17,630
So basically what we're wanting to do is figure out if the value that we are referencing in the array

89
00:08:17,660 --> 00:08:20,150
is part of the left or part of the right.

90
00:08:20,150 --> 00:08:24,200
And if it is, then we want to increment that index by one.

91
00:08:24,650 --> 00:08:32,480
That way we're no longer at the beginning index of that vector.

92
00:08:33,340 --> 00:08:42,130
So now, once we're done with that, we actually have completed this merge sort algorithm.

93
00:08:42,520 --> 00:08:44,470
Everything looks pretty good to me.

94
00:08:44,500 --> 00:08:52,390
We're doing our divide and conquer phase and then we're going to begin merging everything back together.

95
00:08:52,690 --> 00:08:57,550
So if we come back down here, we see that we again, earlier on in this lecture, set up this portion

96
00:08:57,550 --> 00:09:06,760
of the code where we want to take our example from the previous lecture of 473512 and we want to sort

97
00:09:06,760 --> 00:09:06,980
it.

98
00:09:07,000 --> 00:09:15,070
So let's run this and we see down here that we have one, two, three, four, five and seven.

99
00:09:15,190 --> 00:09:21,880
And that is exactly what we did in the previous lecture when we did it by hand.

100
00:09:21,880 --> 00:09:23,470
So that is the correct output.

101
00:09:23,470 --> 00:09:26,350
It's obviously sorted and it's in ascending order.

102
00:09:26,470 --> 00:09:32,170
So hopefully you enjoyed learning how to implement a merge sort algorithm in.

103
00:09:32,890 --> 00:09:39,010
If you have any questions about the implementation, please feel free to ask them in the Q&A section

104
00:09:39,010 --> 00:09:41,740
and I will see you in the next lecture.