1 00:00:06,910 --> 00:00:14,260 In the previous lectures, we have talked about selection sort and bubble sort, two of the easier sort 2 00:00:14,260 --> 00:00:16,960 methods that we can we can learn about. 3 00:00:16,960 --> 00:00:22,060 So now we're going to up the difficulty a little bit and begin talking about merge sort. 4 00:00:22,300 --> 00:00:29,350 And merge sort is an algorithm that is considered to be an example of dividing and conquering. 5 00:00:30,560 --> 00:00:37,250 So this algorithm, what we're going to do is initially divide the array into two equal halves, and 6 00:00:37,250 --> 00:00:39,790 then they are combined in a sorted manner. 7 00:00:39,800 --> 00:00:40,180 Right? 8 00:00:40,190 --> 00:00:51,470 So we're going to divide and conquer and then re merge them back together into a sorted final array. 9 00:00:52,280 --> 00:00:56,030 So let's take a look at what that means. 10 00:00:56,900 --> 00:00:58,820 So a very high level view. 11 00:00:59,660 --> 00:01:03,770 We'll say that we have an array of four seven. 12 00:01:04,490 --> 00:01:07,380 Three, five. 13 00:01:07,400 --> 00:01:09,290 One and two. 14 00:01:09,590 --> 00:01:13,130 So this is our initial array right here. 15 00:01:14,030 --> 00:01:21,770 So we have our all of our elements, and we know that this is going to be a divide and conquer. 16 00:01:22,580 --> 00:01:28,940 So we will say we're going to divide right here at the midpoint. 17 00:01:29,570 --> 00:01:32,210 So divide the array and a half. 18 00:01:32,540 --> 00:01:36,350 So now we have two arrays, four, seven, three. 19 00:01:39,790 --> 00:01:41,020 And five. 20 00:01:41,020 --> 00:01:42,520 One, two. 21 00:01:45,750 --> 00:01:52,620 So again, this is very high level and then we will go over a little bit more in depth after we get 22 00:01:52,620 --> 00:01:53,940 this high level view and. 23 00:01:54,860 --> 00:01:55,640 Out the way. 24 00:01:56,090 --> 00:02:07,190 So now we have divided our initial array and now we want to conquer in a way aka sorted, and then we 25 00:02:07,190 --> 00:02:08,660 want to merge it back together. 26 00:02:08,840 --> 00:02:11,990 So now we're going to sort it. 27 00:02:11,990 --> 00:02:16,620 So three, four, seven, and then one, two, five. 28 00:02:16,640 --> 00:02:18,770 Again, these are their own arrays. 29 00:02:22,950 --> 00:02:28,110 And now that we know that these have been sorted, we want to merge it back together. 30 00:02:29,550 --> 00:02:36,150 So one, two, three, four, five, seven. 31 00:02:36,720 --> 00:02:41,670 So now we have merged them back together and we just executed. 32 00:02:43,680 --> 00:02:44,390 Merge sort. 33 00:02:46,560 --> 00:02:54,360 So how can we eloquently kind of evaluate how this works? 34 00:02:55,230 --> 00:02:58,930 Well, we're going to have a couple of things that we need to do. 35 00:02:58,950 --> 00:03:04,440 So with this being if you might have kind of saw it. 36 00:03:04,770 --> 00:03:12,570 This is actually going to be a recursive algorithm because we're going to continuously divide and conquer. 37 00:03:12,750 --> 00:03:21,810 So we will continuously call on one of our functions in order to continuously break down our array until 38 00:03:21,810 --> 00:03:31,680 we have a very basic one, maybe two element array that we can very quickly sort and then start unwinding 39 00:03:31,680 --> 00:03:35,310 the stack and merging everything back together. 40 00:03:35,610 --> 00:03:39,690 So we're going to have a base case where the array length. 41 00:03:41,720 --> 00:03:42,210 Loop. 42 00:03:43,130 --> 00:03:49,160 The array length is equal to zero or one. 43 00:03:50,360 --> 00:04:02,630 And then the steps that we want to do is we want to break the array in half. 44 00:04:05,160 --> 00:04:06,240 Call. 45 00:04:08,090 --> 00:04:10,340 Merge sort. 46 00:04:12,040 --> 00:04:13,900 On both halves. 47 00:04:19,790 --> 00:04:23,690 And then lastly, the most important part. 48 00:04:23,840 --> 00:04:27,500 We want to merge the two sorted arrays. 49 00:04:33,120 --> 00:04:43,290 Okay, So now let's look back at our initial example because we want to see how this works, obviously, 50 00:04:43,290 --> 00:04:48,120 throughout the entire the entire process. 51 00:04:48,120 --> 00:04:55,620 So let's give let's give ourselves some additional space down here and let's leave our base case and 52 00:04:55,620 --> 00:04:56,250 everything. 53 00:04:56,250 --> 00:04:58,350 That way we can kind of see what we're working with. 54 00:04:58,920 --> 00:05:00,780 So our array 55 00:05:03,090 --> 00:05:07,080 was what was what did we have? 56 00:05:07,080 --> 00:05:09,270 473512. 57 00:05:10,200 --> 00:05:16,800 So we want to sort 473512. 58 00:05:17,760 --> 00:05:20,970 So I went ahead and kind of split it up because we already know that that's what we're going to need 59 00:05:20,970 --> 00:05:21,510 to do. 60 00:05:22,380 --> 00:05:24,390 So we have our two arrays right here. 61 00:05:26,010 --> 00:05:30,630 Well, what we're going to want to do here is split this array up. 62 00:05:30,630 --> 00:05:34,500 So our midpoint is going to be this seven. 63 00:05:34,500 --> 00:05:41,520 So what we'll do is we'll create an array with four and seven, and then we'll have a three here. 64 00:05:41,760 --> 00:05:46,410 Well, obviously three is sorted because that is its own array with one element. 65 00:05:46,410 --> 00:05:49,050 So that satisfies our base case. 66 00:05:49,410 --> 00:05:54,360 But four and seven, we can split it up even more. 67 00:05:54,540 --> 00:05:57,570 We can split it up into four and seven. 68 00:05:58,020 --> 00:06:03,120 So now we know that four and seven are sorted and our base case is satisfied. 69 00:06:03,450 --> 00:06:06,960 So we can also begin working on this one. 70 00:06:07,710 --> 00:06:11,310 So we will have five and one and then two. 71 00:06:11,310 --> 00:06:16,740 Obviously two was sorted and now we will have an array of five and one here as well. 72 00:06:17,550 --> 00:06:25,140 So we now have a total of six arrays technically of four, seven, three, five, one and two. 73 00:06:25,770 --> 00:06:27,030 And now that we. 74 00:06:28,040 --> 00:06:29,360 Have called Merge. 75 00:06:29,360 --> 00:06:30,770 Sort on everything. 76 00:06:30,770 --> 00:06:35,990 We want to begin merging all of our sorted arrays. 77 00:06:36,590 --> 00:06:40,190 So down here we know that four and seven. 78 00:06:40,190 --> 00:06:46,970 So up as we unwind our sorted array here is going to be four and seven. 79 00:06:47,960 --> 00:06:50,140 And now we're at the level where we have the three. 80 00:06:50,150 --> 00:06:52,550 So we're going to merge the three back in. 81 00:06:52,940 --> 00:06:59,810 So now we know that we're going to have three, four and seven, and that's going to be our final array 82 00:06:59,840 --> 00:07:00,350 there. 83 00:07:01,430 --> 00:07:11,480 Over here we're going to have one and five and now we need to sort in the two. 84 00:07:11,810 --> 00:07:16,040 So up here, we're going to go 1 to 5. 85 00:07:16,250 --> 00:07:28,130 So now we have our last two arrays that need to be sorted and they will obviously sort to one, two, 86 00:07:28,130 --> 00:07:33,290 three, four, five and seven. 87 00:07:34,190 --> 00:07:41,300 So as you can see, the complexity of this algorithm is a little bit more difficult than our previous 88 00:07:41,300 --> 00:07:44,990 two in bubble sort and selection sort. 89 00:07:46,250 --> 00:07:50,140 But hopefully you have a good understanding of how this is going to work. 90 00:07:50,150 --> 00:07:55,460 And now we will begin implementing this algorithm in the next lecture.