1 00:00:00,520 --> 00:00:03,680 Once we run this split function recursively over the array, 2 00:00:03,680 --> 00:00:07,910 we should end up with several single member or MT arrays. 3 00:00:07,910 --> 00:00:12,154 At this point, we need to merge them all back and sort them in the process, 4 00:00:12,154 --> 00:00:14,492 which is what our merge function is for. 5 00:00:14,492 --> 00:00:18,685 The merge function is going to take two arrays or a list as arguments, and 6 00:00:18,685 --> 00:00:22,330 to match the naming conventions we used in the split function, 7 00:00:22,330 --> 00:00:24,703 we'll call this left and right as well. 8 00:00:24,703 --> 00:00:30,180 So I'll say def merge, it takes a left and a right list. 9 00:00:30,180 --> 00:00:33,745 Now like before, let's add some documentation to our function. 10 00:00:33,745 --> 00:00:37,692 So this function merges to lists or 11 00:00:37,692 --> 00:00:42,950 arrays, sorting them in the process. 12 00:00:42,950 --> 00:00:48,201 And then it returns a new merged list. 13 00:00:48,201 --> 00:00:51,960 Since our function is going to return a new list, let's start by creating one. 14 00:00:53,900 --> 00:00:59,150 Now in the process of merging, we need to sort the values in both lists. 15 00:00:59,150 --> 00:01:03,600 To sort, we need to compare values from each array, or each list. 16 00:01:03,600 --> 00:01:08,427 So next, let's create two local variables to keep track of index values 17 00:01:08,427 --> 00:01:10,653 that we're using for each list. 18 00:01:10,653 --> 00:01:14,487 So the convention here is i and j, so we'll stick to it. 19 00:01:14,487 --> 00:01:16,684 So i = 0, j = 0. 20 00:01:16,684 --> 00:01:19,834 As we inspect each value in either list, 21 00:01:19,834 --> 00:01:25,313 we'll use the variables to keep track of the indexes of those values. 22 00:01:25,313 --> 00:01:29,670 So we'll use i to keep track of indexes in the left list, and j for 23 00:01:29,670 --> 00:01:31,550 indexes in the right list. 24 00:01:31,550 --> 00:01:35,617 When merging, we want to keep sorting the values 25 00:01:35,617 --> 00:01:39,098 until we've worked through both lists. 26 00:01:39,098 --> 00:01:44,062 So for our loop, let's set up two conditions with an and operator. 27 00:01:44,062 --> 00:01:48,835 So let's say, while, let's see up here, 28 00:01:48,835 --> 00:01:53,995 while i is less than the length of the left list, 29 00:01:53,995 --> 00:01:59,026 and j is less than the length of the right list, 30 00:01:59,026 --> 00:02:03,830 then we'll keep executing our loop. 31 00:02:03,830 --> 00:02:08,670 So here, we're ensuring that as long as i is less than the length of the left list, 32 00:02:08,670 --> 00:02:13,460 and, the and is an important, and j is less than the length of the right list, 33 00:02:13,460 --> 00:02:16,045 we're going to keep executing the code. 34 00:02:16,045 --> 00:02:21,188 Now, i and j are both set 0 initially which means that our first comparison 35 00:02:21,188 --> 00:02:25,857 operation would be on the first element of each list respectively. 36 00:02:25,857 --> 00:02:28,846 So we'll say if left(i), so i 0, so 37 00:02:28,846 --> 00:02:34,836 this is going to get the first value of the left list, is less than right[j]. 38 00:02:34,836 --> 00:02:42,520 And again here, j is 0, so we're going to get the first value out of the right list. 39 00:02:42,520 --> 00:02:47,241 Now, if the value at index i in the left list is less than the value 40 00:02:47,241 --> 00:02:50,940 at index j in the right list, what do we do? 41 00:02:50,940 --> 00:02:55,764 Well that means the value being compared in the left is less than the value in 42 00:02:55,764 --> 00:02:59,747 the right and can be placed at position 0 in the new array, l, 43 00:02:59,747 --> 00:03:01,445 that we created earlier. 44 00:03:01,445 --> 00:03:07,100 So here we'll say l.append(left[i]. 45 00:03:07,100 --> 00:03:13,036 Since we've read and done something with the value at position i, 46 00:03:13,036 --> 00:03:15,793 let's increment that value. 47 00:03:15,793 --> 00:03:20,609 So we move forward to evaluate the next item in the left list. 48 00:03:22,888 --> 00:03:25,545 I + 1 or we can say i += 1. 49 00:03:25,545 --> 00:03:29,151 Okay, next is an else statement. 50 00:03:29,151 --> 00:03:32,655 And here we'll say, if the value at index i, so 51 00:03:32,655 --> 00:03:37,575 I don't have to write out the actual logic because it's implied. 52 00:03:37,575 --> 00:03:41,930 So here we're saying that the value at left is less than the value at right. 53 00:03:41,930 --> 00:03:46,273 Now in the else clause, if the value, so i equal is greater, and 54 00:03:46,273 --> 00:03:50,544 I haven't written out that condition because it's implied. 55 00:03:50,544 --> 00:03:54,199 So here we're saying if the value in the left is less than the value in the right. 56 00:03:54,199 --> 00:03:57,321 So in the else clause, it's going to mean that the value in 57 00:03:57,321 --> 00:04:00,844 the left is either greater than or equal to the value in the right. 58 00:04:00,844 --> 00:04:03,319 But when we hit the else clause, 59 00:04:03,319 --> 00:04:08,175 if the value at index i in the left list is greater, then we place 60 00:04:08,175 --> 00:04:13,233 the value at index j from the right list at the start of the new one. 61 00:04:13,233 --> 00:04:16,593 We list l, and similarly increment j. 62 00:04:16,593 --> 00:04:19,334 So here we'll say, 63 00:04:19,334 --> 00:04:25,793 l.append(right[j]) and then j = j + 1. 64 00:04:27,051 --> 00:04:30,096 Doing this doesn't necessarily mean that in one step, 65 00:04:30,096 --> 00:04:32,309 we'll have a completely sorted array. 66 00:04:32,309 --> 00:04:37,160 But remember that because we start with single element arrays, and combine with 67 00:04:37,160 --> 00:04:41,740 each merge step, we will eventually sort all the values more than one time. 68 00:04:41,740 --> 00:04:47,548 And by the time the entire process is done, all the values are correctly sorted. 69 00:04:47,548 --> 00:04:50,962 Now this isn't all we need to do in the merge step however. 70 00:04:50,962 --> 00:04:53,540 There are two situations we can run into, 71 00:04:53,540 --> 00:04:57,676 one where the left array is larger than the right, and visa versa. 72 00:04:57,676 --> 00:05:02,566 So this can occur when an array containing an odd number of elements needs to be 73 00:05:02,566 --> 00:05:03,104 split. 74 00:05:03,104 --> 00:05:05,897 So how do you split a three element array or list? 75 00:05:05,897 --> 00:05:09,176 Well the left can have two elements and the right can have one, or 76 00:05:09,176 --> 00:05:10,350 the other way around. 77 00:05:10,350 --> 00:05:15,110 In either case, our while loop uses an and condition where the variables 78 00:05:15,110 --> 00:05:19,651 used to store the indexes need to be less than the length of the lists. 79 00:05:19,651 --> 00:05:23,750 If the left list is shorter than the right, then the first condition returns 80 00:05:23,750 --> 00:05:28,560 false, and the entire loop returns false because it's an and condition. 81 00:05:28,560 --> 00:05:32,310 This means that in such an event, when the while loop terminates, not 82 00:05:32,310 --> 00:05:37,100 all the values in the right list will have been moved over to the new combined list. 83 00:05:37,100 --> 00:05:40,920 So to account for this, let's add two more while loops. 84 00:05:40,920 --> 00:05:43,320 The first while loop is going to account for 85 00:05:43,320 --> 00:05:47,990 a situation where the write list is shorter than the left. 86 00:05:47,990 --> 00:05:50,015 And the previous loop terminated, 87 00:05:50,015 --> 00:05:52,925 because we reached the end of the write list first. 88 00:05:52,925 --> 00:05:56,159 So in this case, what we're going to do is simply add 89 00:05:56,159 --> 00:05:59,329 the remaining elements in the left to the new list. 90 00:05:59,329 --> 00:06:03,293 We're not going to compare elements because we're going to assume that within 91 00:06:03,293 --> 00:06:05,315 a list the elements are already sorted. 92 00:06:05,315 --> 00:06:11,126 So while i < len(left): then it's 93 00:06:11,126 --> 00:06:19,495 the same logic l.append(left[i]) and i += 1. 94 00:06:19,495 --> 00:06:23,080 So the while loop is going to have the similar condition. 95 00:06:23,080 --> 00:06:26,350 Keep the loop going until it's at the last index. 96 00:06:26,350 --> 00:06:30,650 Inside the body we're incrementing the index with every iteration of the loop. 97 00:06:30,650 --> 00:06:32,040 Our final loop accounts for 98 00:06:32,040 --> 00:06:36,130 the opposite scenario where the left was shorter than the right. 99 00:06:36,130 --> 00:06:39,047 The only difference here is that we are going to use the variable, 100 00:06:39,047 --> 00:06:40,327 j a long with the right list. 101 00:06:40,327 --> 00:06:47,356 So I'll say while, j < len(right), 102 00:06:47,356 --> 00:06:54,605 l.append(right[j]) and j +=1. 103 00:06:54,605 --> 00:06:56,381 Okay, let's stop here. 104 00:06:56,381 --> 00:06:59,070 In the next video, let's test out merge sort. 105 00:06:59,070 --> 00:07:02,442 Make sure our code is running correctly and everything is written well. 106 00:07:02,442 --> 00:07:05,604 And then we'll wrap up this stage by documenting our code and 107 00:07:05,604 --> 00:07:07,839 evaluating the run time of our algorithm.