Heads up! To view this whole video, sign in with your Courses account or enroll in your free 7-day trial. Sign In Enroll
Preview
Start a free Courses trial
to watch this video
In this video let's write the first bit of logic in our merge sort algorithm - the dividing into sublists.
This video doesn't have any notes.
Related Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign upRelated Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign up
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 upYou need to sign up for Treehouse in order to set up Workspace
Sign up