Splitting Into Sublists3:14 with Pasan Premaratne
In this video let's write the first bit of logic in our merge sort algorithm - the dividing into sublists.
The first bit of logic we are going to write is the divide step of the algorithm. 0:00 This step is fairly straight forward and only requires a few lines of code, but 0:04 is essential to get the sorting process going. 0:09 All right, so as we saw earlier, we are going to call the function for 0:11 the divide step split. 0:15 So we'll say def split, and split is going to take as an argument a list to split up. 0:16 Let's document how this function works. 0:23 So I'll say, divide the unsorted list at midpoint into sublists. 0:26 And it's always good to say, what we're returning as well. 0:35 So I'll say returns to sublists, left and right. 0:38 All right, so the first step is to determine the midpoint of this list, 0:45 of this array. 0:50 We're going to use the floor division operator for this. 0:50 Floor division carries out a division operation and 0:54 if we get a non-integer value like 2.5 back, it just gets rounded down to 2. 0:58 We'll define the midpoint to be the length of the list divided by 2 and 1:04 then rounded down. 1:08 So len(list) and using the two forward slashes for 1:09 the floor division operator, we'll put number 2 after it. 1:14 Okay, once we have the midpoint, we can use the slicing notation in Python, 1:19 to extract portions of the list we want to return. 1:25 For instance, we can define left as the left sublist that 1:29 goes all the way from the start of the list, 1:34 all the way up to the midpoint without including the midpoint. 1:37 Now, over here we are using this slicing syntax, 1:42 where it's like using the subscript notation to access a value from a list. 1:45 But instead, we gave two index values as a start and stop. 1:50 If we don't include a start value as I've done here, 1:55 Python interprets that as starting from the zeroth index or the start of the list. 1:58 As similarly, we can define right to be values on the right of the midpoint. 2:04 So starting at the midpoint and going all the way up to the end of the list. 2:11 So couple things to note, as I said earlier, when you don't include 2:16 the starting index, it interprets it as to start at the very beginning of the list. 2:20 The index you give as the stopping condition, 2:24 that value is not included in the slice. 2:27 So over here we're starting at the very beginning of list, and 2:30 we go all the way up to midpoint, but not including midpoint. 2:34 And then write start at midpoint, so it includes the value and 2:37 then goes all the way to the end of the list. 2:41 Now, once we have these two sublists, we can return them. 2:43 So we return left and right. 2:48 Notice that we're returning two values here and 2:50 then in the merge to spot function, 2:54 when we call that split function we're declaring two variables, left half and 2:56 right half, to assign so that we can assign these two sublists to them, okay? 3:01 And that's all there is to these split function. 3:06 In the next video, let's implement the crucial portion of the merge short logic. 3:09
You need to sign up for Treehouse in order to download course files.Sign up