Ensuring the Correctness of Merge Sort

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