**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.

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 up