In the last video we completed our implementation for

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

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

You can put whatever you want in there, but

make sure that the numbers are not in order.

I will call mine alist.

And here, we'll say, 54, 26 or

62, doesn't matter, 93, 17, 77, 31.

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

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

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

And then if it works correctly,

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

So I'm gonna hit Save.

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

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

I'll hit Enter anyway.

And you should see the error pop up.

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

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

numbers after carrying out all this logic.

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

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

try that one more time.

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

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

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

So we'll bring this back down.

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

And this will take a list.

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

We'll check the length of the list.

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

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

So we'll say if n == 0 or

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

We've verified that it's sorted.

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

actually do quite a bit of work.

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

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

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

the second element in the list.

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

But this isn't sufficient.

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

elements in the list.

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

operator to add on one more condition.

For this condition,

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

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

going from the second element all the way to the end.

Let's visualize how this would work.

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

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

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

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

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

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

An and operator requires both conditions to be true for

the entire line of code to return true.

Since the first condition evaluates to false,

we don't need to bother evaluating the second.

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

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

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

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

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

the element that was the second element in the original list,

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

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

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

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

other than the first 2 elements.

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

we have it already.

It's that first if condition.

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

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

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

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

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

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

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

So let's use this function.

At the bottom, we'll say, print(verify_sorted,

and first we'll pass in (alist).

Oops, we got rid of that, didn't we?

Okay, let me write it out again.

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

so we'll say [54, 26, 93 Okay,

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

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

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

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

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

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

And there we go, it returned false for alist,

meaning it's not sorted but l is sorted.

Cool, so our merge_sort function works.

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