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
In this video let's write the first bit of logic in our merge sort algorithm  the dividing into sublists.

0:00
The first bit of logic we are going to write is the divide step of the algorithm.

0:04
This step is fairly straight forward and only requires a few lines of code, but

0:09
is essential to get the sorting process going.

0:11
All right, so as we saw earlier, we are going to call the function for

0:15
the divide step split.

0:16
So we'll say def split, and split is going to take as an argument a list to split up.

0:23
Let's document how this function works.

0:26
So I'll say, divide the unsorted list at midpoint into sublists.

0:35
And it's always good to say, what we're returning as well.

0:38
So I'll say returns to sublists, left and right.

0:45
All right, so the first step is to determine the midpoint of this list,

0:50
of this array.

0:50
We're going to use the floor division operator for this.

0:54
Floor division carries out a division operation and

0:58
if we get a noninteger value like 2.5 back, it just gets rounded down to 2.

1:04
We'll define the midpoint to be the length of the list divided by 2 and

1:08
then rounded down.

1:09
So len(list) and using the two forward slashes for

1:14
the floor division operator, we'll put number 2 after it.

1:19
Okay, once we have the midpoint, we can use the slicing notation in Python,

1:25
to extract portions of the list we want to return.

1:29
For instance, we can define left as the left sublist that

1:34
goes all the way from the start of the list,

1:37
all the way up to the midpoint without including the midpoint.

1:42
Now, over here we are using this slicing syntax,

1:45
where it's like using the subscript notation to access a value from a list.

1:50
But instead, we gave two index values as a start and stop.

1:55
If we don't include a start value as I've done here,

1:58
Python interprets that as starting from the zeroth index or the start of the list.

2:04
As similarly, we can define right to be values on the right of the midpoint.

2:11
So starting at the midpoint and going all the way up to the end of the list.

2:16
So couple things to note, as I said earlier, when you don't include

2:20
the starting index, it interprets it as to start at the very beginning of the list.

2:24
The index you give as the stopping condition,

2:27
that value is not included in the slice.

2:30
So over here we're starting at the very beginning of list, and

2:34
we go all the way up to midpoint, but not including midpoint.

2:37
And then write start at midpoint, so it includes the value and

2:41
then goes all the way to the end of the list.

2:43
Now, once we have these two sublists, we can return them.

2:48
So we return left and right.

2:50
Notice that we're returning two values here and

2:54
then in the merge to spot function,

2:56
when we call that split function we're declaring two variables, left half and

3:01
right half, to assign so that we can assign these two sublists to them, okay?

3:06
And that's all there is to these split function.

3:09
In the next video, let's implement the crucial portion of the merge short logic.
You need to sign up for Treehouse in order to download course files.
Sign up