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