Heads up! To view this whole video, sign in with your Courses account or enroll in your free 7-day trial. Sign In Enroll
Well done!
You have completed Introduction to Data Structures!
You have completed Introduction to Data Structures!
Preview
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