Preview
Video Player
00:00
00:00
The Divide Step
7:25The 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