The Divide Step7:25 with Pasan Premaratne
The next step in the merge sort algorithm is the divide step, or rather an implementation of the split function.
The next step in the merge sort algorithm is the divide step, or 0:00 rather an implementation of the split function. 0:04 Down here we'll call this split like before and 0:07 this is going to take a linked_list. 0:10 Documenting things is good and we've been doing it so far, so lets add a doc strong. 0:15 Divide the unsorted list at midpoint into sublists. 0:20 Now, of course, when I say sublists here, I mean sub-linked lists, but 0:28 that's a long word to say. 0:32 Now, here's where things start to deviate from the previous version. 0:34 With the list type, we could rely on the fact that finding the midpoint 0:38 using an index and list splicing to split it into two lists would work, 0:42 even if an empty list was passed in. 0:47 Since we have no automatic behavior like that, we need to account for 0:49 this when using a linked list. 0:53 So our first condition, is if the linked list is none, or if it's empty, 0:55 that is, if head is equal to none, we'll say if linked list == None, 1:01 or you can write is there, doesn't matter, or linked_list.head == None. 1:06 Well, linked list can be none, for example, 1:13 if we call split on a linked list containing a single node. 1:15 A split on such a list would mean left would contain the single node 1:18 while right would be none. 1:22 In either case, we're going to assign the entire list to the left half and 1:25 assign none to the right. 1:29 So I'll say left_half = linked_list and 1:31 then right_half = none. 1:37 You could also assign the single element list or none to left and then create 1:40 a new empty linked list assigned to the right half, but that's unnecessary work. 1:45 So now that we've done this, we can return left_half and right_half. 1:50 So that's our first condition. 1:57 Let's add an else clause to account for non-empty linked lists. 1:59 First, we'll calculate the size of the list. 2:03 This is easy because we've done the work already, and 2:06 we can just call the size method that we've defined. 2:09 We'll say size = linked_list.size. 2:12 Using the size we can determine the midpoint. 2:17 So mid = size, and we'll use that floor division operator to divide it by 2. 2:19 Once we have the midpoint, we need to get the node at that midpoint. 2:25 Now, make sure you hit Cmd+S to save here. 2:29 And we're going to navigate back to linked_list.py. 2:32 In here, we're going to add a convenience 2:37 method at the very bottom right before the repr function right here. 2:40 And this convenience method is going to return a node at a given index. 2:44 So we'll call this node_at_index, and 2:49 it's going to take an index value. 2:54 This way, instead of having to traverse a list inside of our split function, 2:57 we can simply call node at index and pass it the midpoint index we calculated 3:02 to give us the node right there so we can perform the split. 3:06 Okay, so 3:09 this method accepts as an argument the index we want to get the node for. 3:10 If this index is 0 then we'll return the head of the list. 3:15 So if index == 0 return self.head. 3:18 The rest of the implementation involves traversing the linked list, 3:24 and counting up to the index as we visit each node. 3:29 The rest of the implementation involves traversing the link list and 3:33 counting up to the index as we visit each node. 3:37 So I'll add an else clause here, and we'll start at the head. 3:41 So we'll say current = self.head. 3:44 Let's also declare a variable called position to indicate 3:47 where we are in the list. 3:52 We can use a while loop to walk down the list. 3:54 Our condition here is as long as the position is less than the index value. 3:57 So I'll say while position is less than index. 4:02 Inside the loop, we'll assign the next node to current and 4:09 increment the value of position by 1. 4:13 So current = current.next_node position += 1. 4:15 Once the position value equals the index value, 4:24 current refers to the node we're looking for, and we can return it. 4:28 We'll say return current. 4:32 Let's get rid of all this empty space. 4:36 There we go. 4:38 Now, back in linked_list merge_sort.py, we can use this method to get at the node 4:39 after we've calculated the midpoint to get the node at the midpoint of the list. 4:46 So we'll say mid_node = linked_list.node_at_index, 4:52 and here I'm gonna do something slightly confusing. 4:58 I'm gonna do mid-1. 5:03 Remember, we're subtracting 1 here because we used size to calculate the midpoint. 5:05 And like the lend function, 5:13 size will always return a value greater than the maximum index value. 5:15 So think of a linked list with two nodes. 5:20 Size would return 2. 5:23 The midpoint, though, and the way we're calculating the index, 5:25 we always start at 0, which means size is going to be 1 greater than that. 5:28 So we're going to deduct 1 from it to get the value we want. 5:32 But we're using the floor division operator, so 5:35 it's going to round that down even more, no big deal. 5:38 With the node at the midpoint, now that we have this midnode, 5:40 we can actually split the list. 5:44 So first, we're going to assign the entire linked list to 5:46 a variable named left_half, so left_half = linked_list. 5:50 This seems counterintuitive, but will make sense in a second. 5:55 For the right_half we're going to assign a new instance of linked_list, 5:58 so right_half = linked_list. 6:04 This newly created list is empty, but 6:08 we can fix that by assigning the node that comes after the midpoint. 6:10 So after the midpoint of the original link list, we can assign the node that comes 6:15 after that midpoint node as the head of this newly created right linked list. 6:19 So here we'll say right_half.head = mid_node.next_node. 6:24 Once we do that, we can assign none to the next node property 6:32 on mid_node to effectively sever that connection, and 6:37 make what was the mid node now the tail node of the left linked list. 6:40 So I'll say mid_node.next_node = None. 6:46 If that's confusing, here's a quick visualization of what just happened. 6:51 We start off with a single linked list and find the midpoint. 6:56 The node that comes after the node at midpoint is assigned to the head of 7:00 a newly created linked list, and the connection between the midpoint node and 7:04 the one after is removed. 7:08 We now have two distinct linked lists, split at the midpoint. 7:10 And with that, we can return the two sub-lists. 7:15 So we'll return left_half and right_half. 7:19 In the next video, let's tackle our merge function. 7:22
You need to sign up for Treehouse in order to download course files.Sign up