Recursively Merging Sublists7:07 with Pasan Premaratne
Once we run the split function recursively over the array we should end up with several single member or empty arrays. At this point we need to merge them all back and sort them in the process which is what our merge function is for.
Once we run this split function recursively over the array, 0:00 we should end up with several single member or MT arrays. 0:03 At this point, we need to merge them all back and sort them in the process, 0:07 which is what our merge function is for. 0:12 The merge function is going to take two arrays or a list as arguments, and 0:14 to match the naming conventions we used in the split function, 0:18 we'll call this left and right as well. 0:22 So I'll say def merge, it takes a left and a right list. 0:24 Now like before, let's add some documentation to our function. 0:30 So this function merges to lists or 0:33 arrays, sorting them in the process. 0:37 And then it returns a new merged list. 0:42 Since our function is going to return a new list, let's start by creating one. 0:48 Now in the process of merging, we need to sort the values in both lists. 0:53 To sort, we need to compare values from each array, or each list. 0:59 So next, let's create two local variables to keep track of index values 1:03 that we're using for each list. 1:08 So the convention here is i and j, so we'll stick to it. 1:10 So i = 0, j = 0. 1:14 As we inspect each value in either list, 1:16 we'll use the variables to keep track of the indexes of those values. 1:19 So we'll use i to keep track of indexes in the left list, and j for 1:25 indexes in the right list. 1:29 When merging, we want to keep sorting the values 1:31 until we've worked through both lists. 1:35 So for our loop, let's set up two conditions with an and operator. 1:39 So let's say, while, let's see up here, 1:44 while i is less than the length of the left list, 1:48 and j is less than the length of the right list, 1:53 then we'll keep executing our loop. 1:59 So here, we're ensuring that as long as i is less than the length of the left list, 2:03 and, the and is an important, and j is less than the length of the right list, 2:08 we're going to keep executing the code. 2:13 Now, i and j are both set 0 initially which means that our first comparison 2:16 operation would be on the first element of each list respectively. 2:21 So we'll say if left(i), so i 0, so 2:25 this is going to get the first value of the left list, is less than right[j]. 2:28 And again here, j is 0, so we're going to get the first value out of the right list. 2:34 Now, if the value at index i in the left list is less than the value 2:42 at index j in the right list, what do we do? 2:47 Well that means the value being compared in the left is less than the value in 2:50 the right and can be placed at position 0 in the new array, l, 2:55 that we created earlier. 2:59 So here we'll say l.append(left[i]. 3:01 Since we've read and done something with the value at position i, 3:07 let's increment that value. 3:13 So we move forward to evaluate the next item in the left list. 3:15 I + 1 or we can say i += 1. 3:22 Okay, next is an else statement. 3:25 And here we'll say, if the value at index i, so 3:29 I don't have to write out the actual logic because it's implied. 3:32 So here we're saying that the value at left is less than the value at right. 3:37 Now in the else clause, if the value, so i equal is greater, and 3:41 I haven't written out that condition because it's implied. 3:46 So here we're saying if the value in the left is less than the value in the right. 3:50 So in the else clause, it's going to mean that the value in 3:54 the left is either greater than or equal to the value in the right. 3:57 But when we hit the else clause, 4:00 if the value at index i in the left list is greater, then we place 4:03 the value at index j from the right list at the start of the new one. 4:08 We list l, and similarly increment j. 4:13 So here we'll say, 4:16 l.append(right[j]) and then j = j + 1. 4:19 Doing this doesn't necessarily mean that in one step, 4:27 we'll have a completely sorted array. 4:30 But remember that because we start with single element arrays, and combine with 4:32 each merge step, we will eventually sort all the values more than one time. 4:37 And by the time the entire process is done, all the values are correctly sorted. 4:41 Now this isn't all we need to do in the merge step however. 4:47 There are two situations we can run into, 4:50 one where the left array is larger than the right, and visa versa. 4:53 So this can occur when an array containing an odd number of elements needs to be 4:57 split. 5:02 So how do you split a three element array or list? 5:03 Well the left can have two elements and the right can have one, or 5:05 the other way around. 5:09 In either case, our while loop uses an and condition where the variables 5:10 used to store the indexes need to be less than the length of the lists. 5:15 If the left list is shorter than the right, then the first condition returns 5:19 false, and the entire loop returns false because it's an and condition. 5:23 This means that in such an event, when the while loop terminates, not 5:28 all the values in the right list will have been moved over to the new combined list. 5:32 So to account for this, let's add two more while loops. 5:37 The first while loop is going to account for 5:40 a situation where the write list is shorter than the left. 5:43 And the previous loop terminated, 5:47 because we reached the end of the write list first. 5:50 So in this case, what we're going to do is simply add 5:52 the remaining elements in the left to the new list. 5:56 We're not going to compare elements because we're going to assume that within 5:59 a list the elements are already sorted. 6:03 So while i < len(left): then it's 6:05 the same logic l.append(left[i]) and i += 1. 6:11 So the while loop is going to have the similar condition. 6:19 Keep the loop going until it's at the last index. 6:23 Inside the body we're incrementing the index with every iteration of the loop. 6:26 Our final loop accounts for 6:30 the opposite scenario where the left was shorter than the right. 6:32 The only difference here is that we are going to use the variable, 6:36 j a long with the right list. 6:39 So I'll say while, j < len(right), 6:40 l.append(right[j]) and j +=1. 6:47 Okay, let's stop here. 6:54 In the next video, let's test out merge sort. 6:56 Make sure our code is running correctly and everything is written well. 6:59 And then we'll wrap up this stage by documenting our code and 7:02 evaluating the run time of our algorithm. 7:05
You need to sign up for Treehouse in order to download course files.Sign up