Bummer! This is just a preview. You need to be signed in with a Basic account to view the entire video.
Start a free Basic trial
to watch this video
The next step in the merge sort algorithm is the divide step, or rather an implementation of the split function.

0:00
The next step in the merge sort algorithm is the divide step, or

0:04
rather an implementation of the split function.

0:07
Down here we'll call this split like before and

0:10
this is going to take a linked_list.

0:15
Documenting things is good and we've been doing it so far, so lets add a doc strong.

0:20
Divide the unsorted list at midpoint into sublists.

0:28
Now, of course, when I say sublists here, I mean sublinked lists, but

0:32
that's a long word to say.

0:34
Now, here's where things start to deviate from the previous version.

0:38
With the list type, we could rely on the fact that finding the midpoint

0:42
using an index and list splicing to split it into two lists would work,

0:47
even if an empty list was passed in.

0:49
Since we have no automatic behavior like that, we need to account for

0:53
this when using a linked list.

0:55
So our first condition, is if the linked list is none, or if it's empty,

1:01
that is, if head is equal to none, we'll say if linked list == None,

1:06
or you can write is there, doesn't matter, or linked_list.head == None.

1:13
Well, linked list can be none, for example,

1:15
if we call split on a linked list containing a single node.

1:18
A split on such a list would mean left would contain the single node

1:22
while right would be none.

1:25
In either case, we're going to assign the entire list to the left half and

1:29
assign none to the right.

1:31
So I'll say left_half = linked_list and

1:37
then right_half = none.

1:40
You could also assign the single element list or none to left and then create

1:45
a new empty linked list assigned to the right half, but that's unnecessary work.

1:50
So now that we've done this, we can return left_half and right_half.

1:57
So that's our first condition.

1:59
Let's add an else clause to account for nonempty linked lists.

2:03
First, we'll calculate the size of the list.

2:06
This is easy because we've done the work already, and

2:09
we can just call the size method that we've defined.

2:12
We'll say size = linked_list.size.

2:17
Using the size we can determine the midpoint.

2:19
So mid = size, and we'll use that floor division operator to divide it by 2.

2:25
Once we have the midpoint, we need to get the node at that midpoint.

2:29
Now, make sure you hit Cmd+S to save here.

2:32
And we're going to navigate back to linked_list.py.

2:37
In here, we're going to add a convenience

2:40
method at the very bottom right before the repr function right here.

2:44
And this convenience method is going to return a node at a given index.

2:49
So we'll call this node_at_index, and

2:54
it's going to take an index value.

2:57
This way, instead of having to traverse a list inside of our split function,

3:02
we can simply call node at index and pass it the midpoint index we calculated

3:06
to give us the node right there so we can perform the split.

3:09
Okay, so

3:10
this method accepts as an argument the index we want to get the node for.

3:15
If this index is 0 then we'll return the head of the list.

3:18
So if index == 0 return self.head.

3:24
The rest of the implementation involves traversing the linked list,

3:29
and counting up to the index as we visit each node.

3:33
The rest of the implementation involves traversing the link list and

3:37
counting up to the index as we visit each node.

3:41
So I'll add an else clause here, and we'll start at the head.

3:44
So we'll say current = self.head.

3:47
Let's also declare a variable called position to indicate

3:52
where we are in the list.

3:54
We can use a while loop to walk down the list.

3:57
Our condition here is as long as the position is less than the index value.

4:02
So I'll say while position is less than index.

4:09
Inside the loop, we'll assign the next node to current and

4:13
increment the value of position by 1.

4:15
So current = current.next_node position += 1.

4:24
Once the position value equals the index value,

4:28
current refers to the node we're looking for, and we can return it.

4:32
We'll say return current.

4:36
Let's get rid of all this empty space.

4:38
There we go.

4:39
Now, back in linked_list merge_sort.py, we can use this method to get at the node

4:46
after we've calculated the midpoint to get the node at the midpoint of the list.

4:52
So we'll say mid_node = linked_list.node_at_index,

4:58
and here I'm gonna do something slightly confusing.

5:03
I'm gonna do mid1.

5:05
Remember, we're subtracting 1 here because we used size to calculate the midpoint.

5:13
And like the lend function,

5:15
size will always return a value greater than the maximum index value.

5:20
So think of a linked list with two nodes.

5:23
Size would return 2.

5:25
The midpoint, though, and the way we're calculating the index,

5:28
we always start at 0, which means size is going to be 1 greater than that.

5:32
So we're going to deduct 1 from it to get the value we want.

5:35
But we're using the floor division operator, so

5:38
it's going to round that down even more, no big deal.

5:40
With the node at the midpoint, now that we have this midnode,

5:44
we can actually split the list.

5:46
So first, we're going to assign the entire linked list to

5:50
a variable named left_half, so left_half = linked_list.

5:55
This seems counterintuitive, but will make sense in a second.

5:58
For the right_half we're going to assign a new instance of linked_list,

6:04
so right_half = linked_list.

6:08
This newly created list is empty, but

6:10
we can fix that by assigning the node that comes after the midpoint.

6:15
So after the midpoint of the original link list, we can assign the node that comes

6:19
after that midpoint node as the head of this newly created right linked list.

6:24
So here we'll say right_half.head = mid_node.next_node.

6:32
Once we do that, we can assign none to the next node property

6:37
on mid_node to effectively sever that connection, and

6:40
make what was the mid node now the tail node of the left linked list.

6:46
So I'll say mid_node.next_node = None.

6:51
If that's confusing, here's a quick visualization of what just happened.

6:56
We start off with a single linked list and find the midpoint.

7:00
The node that comes after the node at midpoint is assigned to the head of

7:04
a newly created linked list, and the connection between the midpoint node and

7:08
the one after is removed.

7:10
We now have two distinct linked lists, split at the midpoint.

7:15
And with that, we can return the two sublists.

7:19
So we'll return left_half and right_half.

7:22
In the next video, let's tackle our merge function.
You need to sign up for Treehouse in order to download course files.
Sign up