1
00:00:00,000 --> 00:00:03,138
In the last video we completed
our implementation for

2
00:00:03,138 --> 00:00:06,844
the merge_sort algorithm, but
we didn't test it in any way.

3
00:00:06,844 --> 00:00:10,511
Let's define a new list at the bottom
that contains several numbers.

4
00:00:10,511 --> 00:00:13,149
You can put whatever you want in there,
but

5
00:00:13,149 --> 00:00:15,868
make sure that the numbers
are not in order.

6
00:00:15,868 --> 00:00:19,642
I will call mine alist.

7
00:00:19,642 --> 00:00:23,024
And here, we'll say, 54, 26 or

8
00:00:23,024 --> 00:00:27,903
62, doesn't matter, 93, 17, 77, 31.

9
00:00:27,903 --> 00:00:35,669
Just add enough so
that you can make out that it's sorted.

10
00:00:35,669 --> 00:00:42,800
Okay, next we're going to call the
merge_sort algorithm and pass in our list.

11
00:00:42,800 --> 00:00:48,626
Let's assign this to some variables,
so we'll say l = merge_sort(list).

12
00:00:48,626 --> 00:00:51,420
And then if it works correctly,

13
00:00:51,420 --> 00:00:56,807
we should be able to print this list and
see what it looks like.

14
00:00:56,807 --> 00:00:57,909
So I'm gonna hit Save.

15
00:00:57,909 --> 00:01:01,838
Down here in the console,
we'll type out python merge_sort.py.

16
00:01:01,838 --> 00:01:06,365
And before I hit Enter, I actually noticed
I made an error in the last video, but

17
00:01:06,365 --> 00:01:07,796
I'll hit Enter anyway.

18
00:01:07,796 --> 00:01:10,392
And you should see the error pop up.

19
00:01:10,392 --> 00:01:15,153
Okay, so what I forgot to do, which is
a pretty crucial part of our algorithm,

20
00:01:15,153 --> 00:01:19,698
is in the merge function, I forgot to
return the list containing the sorted

21
00:01:19,698 --> 00:01:22,510
numbers after carrying out all this logic.

22
00:01:22,510 --> 00:01:26,488
So here at the bottom, we'll say return l.

23
00:01:26,488 --> 00:01:31,477
All right, we'll save again, and
now, we'll clear this out and

24
00:01:31,477 --> 00:01:34,120
try that one more time.

25
00:01:34,120 --> 00:01:38,120
And there we go.
You should see a sorted list printed out.

26
00:01:38,120 --> 00:01:42,940
We can write out a more robust function
to test this because with bigger arrays,

27
00:01:42,940 --> 00:01:46,840
visually evaluating that printed
list won't always be feasible.

28
00:01:46,840 --> 00:01:49,554
So we'll bring this back down.

29
00:01:49,554 --> 00:01:54,903
Let's get rid of this and
we'll call our function verify_sorted.

30
00:01:54,903 --> 00:01:56,600
And this will take a list.

31
00:01:56,600 --> 00:02:01,084
First we're going to check
inside the body of the function.

32
00:02:01,084 --> 00:02:03,421
We'll check the length of the list.

33
00:02:03,421 --> 00:02:07,548
If the list is a single-element list or
an empty list,

34
00:02:07,548 --> 00:02:14,027
we don't need to do any unnecessary work
because, remember, it is naively sorted.

35
00:02:14,027 --> 00:02:17,535
So we'll say if n == 0 or

36
00:02:17,535 --> 00:02:22,806
if n == 1: then we'll return True.

37
00:02:22,806 --> 00:02:24,049
We've verified that it's sorted.

38
00:02:24,049 --> 00:02:28,928
Now, to conclude our function we're going
to write out one line of code that will

39
00:02:28,928 --> 00:02:30,883
actually do quite a bit of work.

40
00:02:30,883 --> 00:02:36,763
So first we'll say return list[0], so
we'll take the first element of the list

41
00:02:36,763 --> 00:02:43,200
and we'll compare and see if that's less
than the second element in the list.

42
00:02:43,200 --> 00:02:47,186
Okay, so first we'll check that the first
element in the list is less than

43
00:02:47,186 --> 00:02:48,940
the second element in the list.

44
00:02:48,940 --> 00:02:51,973
This returns either true or false,
so we can return that directly.

45
00:02:51,973 --> 00:02:53,957
But this isn't sufficient.

46
00:02:53,957 --> 00:02:58,588
If it were, we could trick the verify
function by only sorting the first two

47
00:02:58,588 --> 00:02:59,993
elements in the list.

48
00:02:59,993 --> 00:03:03,614
So to this return statement,
we're going to use an and

49
00:03:03,614 --> 00:03:06,695
operator to add on one more condition.

50
00:03:06,695 --> 00:03:07,585
For this condition,

51
00:03:07,585 --> 00:03:13,321
we're going to make a recursive
function call back to verify_sorted.

52
00:03:13,321 --> 00:03:17,885
And for the argument,
we're going to pass in the list

53
00:03:17,885 --> 00:03:22,205
going from the second element
all the way to the end.

54
00:03:22,205 --> 00:03:23,631
Let's visualize how this would work.

55
00:03:23,631 --> 00:03:26,737
We'll use a five element
list as an example.

56
00:03:26,737 --> 00:03:30,175
So we'll call verify_sorted and
pass in the entire list.

57
00:03:30,175 --> 00:03:35,128
This list is not 1 or 0 elements long,
so we skip that first if statement.

58
00:03:35,128 --> 00:03:38,888
There's only one line of code
left in the function, and

59
00:03:38,888 --> 00:03:44,170
first we check that the element at index
0 is less than the element at index 1.

60
00:03:44,170 --> 00:03:48,338
If this is false, the function returns
immediately with a false value.

61
00:03:48,338 --> 00:03:51,756
An and operator requires both
conditions to be true for

62
00:03:51,756 --> 00:03:54,221
the entire line of code to return true.

63
00:03:54,221 --> 00:03:57,223
Since the first condition
evaluates to false,

64
00:03:57,223 --> 00:04:00,310
we don't need to bother
evaluating the second.

65
00:04:00,310 --> 00:04:05,138
The second condition is a recursive call
with a sublist containing elements from

66
00:04:05,138 --> 00:04:08,982
the original list starting at
position one and going to the end.

67
00:04:08,982 --> 00:04:13,905
So in the second call, again, we can
skip that first if statement and proceed

68
00:04:13,905 --> 00:04:18,780
to check whether the value at element
0 is less than the value at element 1.

69
00:04:18,780 --> 00:04:23,262
Remember that because this list is
a sublist of the original starting at

70
00:04:23,262 --> 00:04:27,146
the element that was the second
element in the original list,

71
00:04:27,146 --> 00:04:31,104
by comparing the elements at
position 0 and 1 in the sublist,

72
00:04:31,104 --> 00:04:36,579
we're effectively comparing the elements
at position 1 and 2 in the original list.

73
00:04:36,579 --> 00:04:42,432
With each recursive call, as we create new
sublists that start at index position 1,

74
00:04:42,432 --> 00:04:47,393
we're able to check the entire list
without having to specify any checks

75
00:04:47,393 --> 00:04:50,410
other than the first 2 elements.

76
00:04:50,410 --> 00:04:54,682
Since this is a recursive function,
it means we need a stopping condition, and

77
00:04:54,682 --> 00:04:55,783
we have it already.

78
00:04:55,783 --> 00:04:58,093
It's that first if condition.

79
00:04:58,093 --> 00:05:01,952
As we keep making sublists,
once we reach a single-element list,

80
00:05:01,952 --> 00:05:05,959
that element is already sorted by
definition, so we can return true.

81
00:05:05,959 --> 00:05:11,352
Since this recursive function call is part
of an and condition, it means that every

82
00:05:11,352 --> 00:05:16,515
single recursive call has to return true
all the way back to the beginning for our

83
00:05:16,515 --> 00:05:22,560
top level function to return true and for
the function to say yes, this is sorted.

84
00:05:22,560 --> 00:05:26,830
Now, we could have easily done this using
an iterative solution and a for loop.

85
00:05:26,830 --> 00:05:31,450
But this way, you get another example of
recursion to work through and understand.

86
00:05:31,450 --> 00:05:32,350
So let's use this function.

87
00:05:32,350 --> 00:05:37,333
At the bottom, we'll say,
print(verify_sorted,

88
00:05:37,333 --> 00:05:40,650
and first we'll pass in (alist).

89
00:05:40,650 --> 00:05:43,200
Oops, we got rid of that, didn't we?

90
00:05:43,200 --> 00:05:45,126
Okay, let me write it out again.

91
00:05:45,126 --> 00:05:51,729
So alist =, and I think I have those
original numbers here somewhere,

92
00:05:51,729 --> 00:05:57,981
so we'll say [54, 26, 93 Okay,

93
00:05:57,981 --> 00:06:05,056
and then we assign to l the result
of calling merge_sort(alist).

94
00:06:05,056 --> 00:06:10,291
Okay, so now here we're going
to use the verify_sorted

95
00:06:10,291 --> 00:06:15,319
function and
we'll check first that alist is sorted.

96
00:06:15,319 --> 00:06:20,166
That should return false, and
then we'll check the same call on, and

97
00:06:20,166 --> 00:06:23,464
we'll pass in l, and
this should return true.

98
00:06:23,464 --> 00:06:29,083
Okay, so now at the bottom here in the
console we'll call python merge_sort.py.

99
00:06:29,083 --> 00:06:32,370
And there we go,
it returned false for alist,

100
00:06:32,370 --> 00:06:35,740
meaning it's not sorted but l is sorted.

101
00:06:35,740 --> 00:06:38,540
Cool, so our merge_sort function works.

102
00:06:38,540 --> 00:06:41,570
In the next video let's talk
about the cost of this algorithm.