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

Now that we have a working implementation of merge sort, let's write some code to make sure the algorithm runs as expected.

In the last video we completed
our implementation for
0:00

the merge_sort algorithm, but
we didn't test it in any way.
0:03

Let's define a new list at the bottom
that contains several numbers.
0:06

You can put whatever you want in there,
but
0:10

make sure that the numbers
are not in order.
0:13

I will call mine alist.
0:15

And here, we'll say, 54, 26 or
0:19

62, doesn't matter, 93, 17, 77, 31.
0:23

Just add enough so
that you can make out that it's sorted.
0:27

Okay, next we're going to call the
merge_sort algorithm and pass in our list.
0:35

Let's assign this to some variables,
so we'll say l = merge_sort(list).
0:42

And then if it works correctly,
0:48

we should be able to print this list and
see what it looks like.
0:51

So I'm gonna hit Save.
0:56

Down here in the console,
we'll type out python merge_sort.py.
0:57

And before I hit Enter, I actually noticed
I made an error in the last video, but
1:01

I'll hit Enter anyway.
1:06

And you should see the error pop up.
1:07

Okay, so what I forgot to do, which is
a pretty crucial part of our algorithm,
1:10

is in the merge function, I forgot to
return the list containing the sorted
1:15

numbers after carrying out all this logic.
1:19

So here at the bottom, we'll say return l.
1:22

All right, we'll save again, and
now, we'll clear this out and
1:26

try that one more time.
1:31

And there we go.
You should see a sorted list printed out.
1:34

We can write out a more robust function
to test this because with bigger arrays,
1:38

visually evaluating that printed
list won't always be feasible.
1:42

So we'll bring this back down.
1:46

Let's get rid of this and
we'll call our function verify_sorted.
1:49

And this will take a list.
1:54

First we're going to check
inside the body of the function.
1:56

We'll check the length of the list.
2:01

If the list is a single-element list or
an empty list,
2:03

we don't need to do any unnecessary work
because, remember, it is naively sorted.
2:07

So we'll say if n == 0 or
2:14

if n == 1: then we'll return True.
2:17

We've verified that it's sorted.
2:22

Now, to conclude our function we're going
to write out one line of code that will
2:24

actually do quite a bit of work.
2:28

So first we'll say return list[0], so
we'll take the first element of the list
2:30

and we'll compare and see if that's less
than the second element in the list.
2:36

Okay, so first we'll check that the first
element in the list is less than
2:43

the second element in the list.
2:47

This returns either true or false,
so we can return that directly.
2:48

But this isn't sufficient.
2:51

If it were, we could trick the verify
function by only sorting the first two
2:53

elements in the list.
2:58

So to this return statement,
we're going to use an and
2:59

operator to add on one more condition.
3:03

For this condition,
3:06

we're going to make a recursive
function call back to verify_sorted.
3:07

And for the argument,
we're going to pass in the list
3:13

going from the second element
all the way to the end.
3:17

Let's visualize how this would work.
3:22

We'll use a five element
list as an example.
3:23

So we'll call verify_sorted and
pass in the entire list.
3:26

This list is not 1 or 0 elements long,
so we skip that first if statement.
3:30

There's only one line of code
left in the function, and
3:35

first we check that the element at index
0 is less than the element at index 1.
3:38

If this is false, the function returns
immediately with a false value.
3:44

An and operator requires both
conditions to be true for
3:48

the entire line of code to return true.
3:51

Since the first condition
evaluates to false,
3:54

we don't need to bother
evaluating the second.
3:57

The second condition is a recursive call
with a sublist containing elements from
4:00

the original list starting at
position one and going to the end.
4:05

So in the second call, again, we can
skip that first if statement and proceed
4:08

to check whether the value at element
0 is less than the value at element 1.
4:13

Remember that because this list is
a sublist of the original starting at
4:18

the element that was the second
element in the original list,
4:23

by comparing the elements at
position 0 and 1 in the sublist,
4:27

we're effectively comparing the elements
at position 1 and 2 in the original list.
4:31

With each recursive call, as we create new
sublists that start at index position 1,
4:36

we're able to check the entire list
without having to specify any checks
4:42

other than the first 2 elements.
4:47

Since this is a recursive function,
it means we need a stopping condition, and
4:50

we have it already.
4:54

It's that first if condition.
4:55

As we keep making sublists,
once we reach a single-element list,
4:58

that element is already sorted by
definition, so we can return true.
5:01

Since this recursive function call is part
of an and condition, it means that every
5:05

single recursive call has to return true
all the way back to the beginning for our
5:11

top level function to return true and for
the function to say yes, this is sorted.
5:16

Now, we could have easily done this using
an iterative solution and a for loop.
5:22

But this way, you get another example of
recursion to work through and understand.
5:26

So let's use this function.
5:31

At the bottom, we'll say,
print(verify_sorted,
5:32

and first we'll pass in (alist).
5:37

Oops, we got rid of that, didn't we?
5:40

Okay, let me write it out again.
5:43

So alist =, and I think I have those
original numbers here somewhere,
5:45

so we'll say [54, 26, 93 Okay,
5:51

and then we assign to l the result
of calling merge_sort(alist).
5:57

Okay, so now here we're going
to use the verify_sorted
6:05

function and
we'll check first that alist is sorted.
6:10

That should return false, and
then we'll check the same call on, and
6:15

we'll pass in l, and
this should return true.
6:20

Okay, so now at the bottom here in the
console we'll call python merge_sort.py.
6:23

And there we go,
it returned false for alist,
6:29

meaning it's not sorted but l is sorted.
6:32

Cool, so our merge_sort function works.
6:35

In the next video let's talk
about the cost of this algorithm.
6:38

You need to sign up for Treehouse in order to download course files.

Sign up