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.