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
Now that we have a working implementation of merge sort, let's write some code to make sure the algorithm runs as expected.

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

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

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

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

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

0:15
I will call mine alist.

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

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

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

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

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

0:48
And then if it works correctly,

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

0:56
So I'm gonna hit Save.

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

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

1:06
I'll hit Enter anyway.

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

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

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

1:19
numbers after carrying out all this logic.

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

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

1:31
try that one more time.

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

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

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

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

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

1:54
And this will take a list.

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

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

2:03
If the list is a singleelement list or an empty list,

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

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

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

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

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

2:28
actually do quite a bit of work.

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

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

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

2:47
the second element in the list.

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

2:51
But this isn't sufficient.

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

2:58
elements in the list.

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

3:03
operator to add on one more condition.

3:06
For this condition,

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

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

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

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

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

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

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

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

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

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

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

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

3:54
Since the first condition evaluates to false,

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

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

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

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

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

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

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

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

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

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

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

4:47
other than the first 2 elements.

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

4:54
we have it already.

4:55
It's that first if condition.

4:58
As we keep making sublists, once we reach a singleelement list,

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

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

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

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

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

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

5:31
So let's use this function.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6:35
Cool, so our merge_sort function works.

6:38
In the next video let's talk about the cost of this algorithm.
You need to sign up for Treehouse in order to download course files.
Sign up