1 00:00:00,450 --> 00:00:07,740 ‫So in this video we're going to write the code for Merge Sort and we'll start our code out like this. 2 00:00:07,770 --> 00:00:11,850 ‫We're going to pass it an array and the array we're going to pass. 3 00:00:11,850 --> 00:00:20,460 ‫This will be this four item array and then we're going to pass it to indexes left index and right index. 4 00:00:20,790 --> 00:00:28,380 ‫And left index will be that first item at the index of zero and right index will be that last item at 5 00:00:28,380 --> 00:00:30,420 ‫the index of three. 6 00:00:30,810 --> 00:00:37,170 ‫So on the right side of the screen, I'm going to bring up a call stack and I'm going to add an instance 7 00:00:37,170 --> 00:00:43,650 ‫of merge sort where left index is zero and right index is three. 8 00:00:44,100 --> 00:00:52,080 ‫So if you'll recall from the merge function, we had to pass it another index which was called mid index 9 00:00:52,410 --> 00:00:56,490 ‫and we're going to calculate mid index with this equation. 10 00:00:56,790 --> 00:01:02,820 ‫So one of the things I want to point out here is in math, because of order of operations, we have 11 00:01:02,820 --> 00:01:07,110 ‫to do the division before we do the addition. 12 00:01:07,500 --> 00:01:12,540 ‫So if you do the math on this, you'll see that this calculates to 1.5. 13 00:01:12,690 --> 00:01:19,710 ‫But because mid index is an integer, everything to the right of the decimal place gets dropped and 14 00:01:19,710 --> 00:01:21,780 ‫we just keep the whole number. 15 00:01:22,020 --> 00:01:25,980 ‫So mid index will be this item here. 16 00:01:26,400 --> 00:01:33,900 ‫So this one is the integer mid index for this instance of merge sort. 17 00:01:34,260 --> 00:01:40,380 ‫So the next thing merge sort will do is call another instance of merge sorts. 18 00:01:40,380 --> 00:01:45,540 ‫So this is where it is recursive, but it will be on a different range. 19 00:01:45,840 --> 00:01:50,040 ‫So we're going to call this on left index and mid index. 20 00:01:50,400 --> 00:01:54,120 ‫So you can see on the call stack here that left index is zero. 21 00:01:54,120 --> 00:02:00,240 ‫That's this item and mid index is one which is this item. 22 00:02:00,720 --> 00:02:06,120 ‫So that will add another instance of merge sort to the call stack. 23 00:02:06,510 --> 00:02:14,280 ‫But now left index is zero and right index is one and that is this range here. 24 00:02:14,730 --> 00:02:19,500 ‫So now this is the active instance of merge sort on the call stack. 25 00:02:19,740 --> 00:02:26,250 ‫So the first thing this instance of merge sort is going to do is calculate mid index. 26 00:02:26,490 --> 00:02:32,190 ‫And when we calculate this equation, this comes out to 0.5. 27 00:02:32,550 --> 00:02:38,550 ‫But once again, because this is an integer, everything to the right of the decimal places dropped 28 00:02:38,550 --> 00:02:43,680 ‫and mid index for this instance of merge sort is zero. 29 00:02:44,100 --> 00:02:52,830 ‫So now this instance of merge sort has calculated mid index and it moves to this line of code and now 30 00:02:52,830 --> 00:02:57,600 ‫left index and mid index are both zero. 31 00:02:57,600 --> 00:03:06,840 ‫So we're calling merge sort with left and right both equal to zero, which gives us this one item. 32 00:03:07,200 --> 00:03:13,440 ‫And once we get down to a sub array that contains one item, that is our base case. 33 00:03:13,710 --> 00:03:21,270 ‫So I'm going to bring in an if statement above these two lines of code that says if left index is greater 34 00:03:21,270 --> 00:03:25,920 ‫than or equal to right index, we're just going to run, return. 35 00:03:26,130 --> 00:03:29,520 ‫And you can see that left and right index are equal. 36 00:03:29,520 --> 00:03:35,760 ‫So the conditional in this if statement will be true and when we run return, that just pops that from 37 00:03:35,760 --> 00:03:36,750 ‫the call stack. 38 00:03:37,300 --> 00:03:41,670 ‫So now this is the active instance of merge sort on the call stack. 39 00:03:41,680 --> 00:03:47,110 ‫Again, it has run this line of code to calculate mid index. 40 00:03:47,560 --> 00:03:50,660 ‫It ran merge sort on the left. 41 00:03:50,680 --> 00:03:53,980 ‫Now we're going to run merge sort on the right. 42 00:03:54,310 --> 00:03:57,430 ‫So we're going to use mid index plus one. 43 00:03:57,430 --> 00:03:59,320 ‫Mid index is zero. 44 00:03:59,320 --> 00:04:05,140 ‫So mid index plus one is one and then right index is one. 45 00:04:05,260 --> 00:04:11,620 ‫So we'll call an instance of merge sort where left and right are both one, which is this item. 46 00:04:11,980 --> 00:04:17,080 ‫Now this is the active instance of merge sort will run this if statement. 47 00:04:17,290 --> 00:04:23,560 ‫Left index is equal to right index so we run return and that is popped from the call stack. 48 00:04:23,890 --> 00:04:29,500 ‫So now once again, this is the active instance of merge sort on the call stack. 49 00:04:29,500 --> 00:04:32,440 ‫It is run all three of these lines of code. 50 00:04:32,590 --> 00:04:36,730 ‫Which brings us to the last line of code in this function. 51 00:04:37,060 --> 00:04:44,560 ‫Now we're going to run, merge, and now an instance of merge gets added to the call stack. 52 00:04:44,920 --> 00:04:53,230 ‫So notice that with this instance of merge left index and mid index are zero and right index is one. 53 00:04:53,500 --> 00:05:00,340 ‫And notice that the same is true for all three of those for the instance of merge sort that called it. 54 00:05:00,730 --> 00:05:03,010 ‫That will always be the case. 55 00:05:03,280 --> 00:05:11,470 ‫So when you run merge, it's going to do this and once it does that merge is popped from the call stack. 56 00:05:11,710 --> 00:05:17,800 ‫And once that is popped, this once again becomes the active instance on the call stack. 57 00:05:18,190 --> 00:05:25,630 ‫It has run all of these lines of code, which means it's done running and now it will be popped from 58 00:05:25,630 --> 00:05:26,650 ‫the call stack. 59 00:05:26,950 --> 00:05:32,230 ‫And now this becomes the active instance of merge sort on the call stack. 60 00:05:32,380 --> 00:05:38,380 ‫It has already calculated mid index, it ran merge sort on the left. 61 00:05:38,380 --> 00:05:40,990 ‫Now it's going to run it on the right. 62 00:05:41,350 --> 00:05:48,940 ‫So we'll add this to the call stack where left is two and right is three and that is this range here. 63 00:05:49,300 --> 00:05:53,110 ‫So now this is the active instance of merge sort on the call stack. 64 00:05:53,110 --> 00:05:58,900 ‫The first thing we'll do is this if statement the conditional in this if statement will be false. 65 00:05:58,900 --> 00:06:00,970 ‫So we'll move down to this line. 66 00:06:01,300 --> 00:06:04,300 ‫This calculation will yield 2.5. 67 00:06:04,300 --> 00:06:10,720 ‫But because this is an integer, we drop everything to the right of the decimal place and mid index 68 00:06:10,720 --> 00:06:14,020 ‫for this instance of merge sort will be two. 69 00:06:14,560 --> 00:06:21,670 ‫So then we'll move to this line of code which will call merge sort where left index is two and right 70 00:06:21,670 --> 00:06:22,780 ‫index is two. 71 00:06:23,080 --> 00:06:28,510 ‫So we'll add this to the call stack and that is this range here. 72 00:06:28,900 --> 00:06:31,150 ‫So this is the active instance. 73 00:06:31,150 --> 00:06:36,310 ‫Now we'll run this if statement and this conditional will be true. 74 00:06:36,340 --> 00:06:41,020 ‫So we will run return and that will be popped from the call stack. 75 00:06:41,320 --> 00:06:44,590 ‫So now this becomes the active instance on the call stack. 76 00:06:44,590 --> 00:06:49,750 ‫It has run these two lines of code and now we move to this line of code. 77 00:06:49,960 --> 00:06:57,730 ‫So now we're calling merge sort on this range, which is this item and now this is the active instance 78 00:06:57,730 --> 00:06:58,690 ‫of merge sort. 79 00:06:58,690 --> 00:07:05,800 ‫We'll run this if statement for that instance the conditional is true because left index is equal to 80 00:07:05,800 --> 00:07:10,540 ‫right index so we'll run return in that is popped from the call stack. 81 00:07:10,870 --> 00:07:16,360 ‫And now once again this becomes the active instance of merge sort on the call stack. 82 00:07:16,360 --> 00:07:23,800 ‫It is run all three of these lines of code and now it moves to this line of code and we add an instance 83 00:07:23,800 --> 00:07:25,810 ‫of merge to the call stack. 84 00:07:26,140 --> 00:07:32,470 ‫So once again, notice that left index, mid index and right index are the same for this instance of 85 00:07:32,470 --> 00:07:37,210 ‫merge as it is for the instance of merge sort that called it. 86 00:07:37,720 --> 00:07:44,740 ‫So this merge function is going to do this and once it does that it will be popped from the call stack. 87 00:07:45,190 --> 00:07:48,490 ‫So now this becomes the active instance on the call stack. 88 00:07:48,490 --> 00:07:55,090 ‫It has run all four of these lines of code, which means it is done running and it will be popped from 89 00:07:55,090 --> 00:07:56,080 ‫the call stack. 90 00:07:56,440 --> 00:07:59,400 ‫So now this becomes the active instance. 91 00:07:59,410 --> 00:08:07,240 ‫It has run these three lines of code and this instance now moves to this line of code, which adds an 92 00:08:07,240 --> 00:08:09,880 ‫instance of merge to the call stack. 93 00:08:10,060 --> 00:08:17,500 ‫This instance of Merge will do this, and once it does that, that will be popped from the call stack. 94 00:08:17,890 --> 00:08:21,790 ‫This once again becomes the active instance on the call stack. 95 00:08:21,790 --> 00:08:27,850 ‫It has run all of these lines of code, which means it will now be popped from the call stack. 96 00:08:28,240 --> 00:08:34,810 ‫And once that happens, merge sort is done running and we know that this array is sorted. 97 00:08:35,260 --> 00:08:36,820 ‫So we'll look at this code and. 98 00:08:36,900 --> 00:08:44,400 ‫A moment in VS code and when we do we'll start with an array that looks like this and we'll run, merge, 99 00:08:44,400 --> 00:08:46,320 ‫sort and sort it. 100 00:08:46,860 --> 00:08:50,430 ‫So now let's flip over and take a look at this. 101 00:08:51,000 --> 00:08:56,610 ‫So there is our merge helper function that we had written previously and I'll scroll up. 102 00:08:58,240 --> 00:09:06,100 ‫And this is the merge sort function that we just wrote and I'll scroll up again and in our main function 103 00:09:06,100 --> 00:09:10,080 ‫this is the array three one, four two that we're going to sort. 104 00:09:10,330 --> 00:09:13,300 ‫And with this line, we'll calculate the size. 105 00:09:13,390 --> 00:09:20,050 ‫The left index will be zero, and then we'll use the size to calculate the right index. 106 00:09:20,320 --> 00:09:26,650 ‫And then we'll come down here and run, merge, sort on the array and pass at the left and right index. 107 00:09:26,890 --> 00:09:31,450 ‫And then with this four loop will print that out and I'll run this. 108 00:09:32,110 --> 00:09:35,950 ‫And you can see that the array is sorted one through four. 109 00:09:36,590 --> 00:09:41,720 ‫So it looks like we have a working function for merge sort.