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.
This video doesn't have any notes.
Related Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign upRelated Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign up
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 upYou need to sign up for Treehouse in order to set up Workspace
Sign up