The Merge Function

[MUSIC] 0:00 Over the last few videos, we implemented the merge sort algorithm on the array or 0:04 list type in Python. 0:09 Merge sort is probably the most complicated algorithm we've 0:11 written so far. 0:14 But in doing so, we learned about an important concept, divide and conquer. 0:15 We also concluded the last video by figuring 0:19 out the runtime of merge sort based on our implementation. 0:22 Over the next few videos, we're going to implement merge sort again, 0:26 this time on the linked list type. 0:30 In doing so, 0:31 we're going to get a chance to see how the implementation differs based on 0:32 the data structure while still keeping the fundamentals of the algorithm the same. 0:36 And we'll also see how the runtime may be affected by the kinds of operations we 0:40 need to implement. 0:45 Let's create a new file that puts our second implementation of merge sort in. 0:47 So File over here, New File, and this is going to have a rather long name. 0:51 We'll call this linked_list_merge_sort with underscores everywhere .py. 0:56 We're going to need the linked list class that we created earlier, so we'll 1:04 start at the top by importing the linked list class from the linked_list.py file. 1:09 The way we do that is we'll say from linked_list import LinkedList. 1:15 Right, so that imports the class. 1:22 Let's test if this works really quick. 1:24 We'll just do something like l = LinkedList l.add 10 or 1:28 1, doesn't matter, print(l). 1:34 Okay, and if I hit save, and then down here, 1:38 we'll say python linked_list_merge_sort.py. 1:42 Okay, it works. 1:47 So this is how we get some of the code, 1:48 how we reuse the code that we've written in other files into this current file. 1:50 We can get rid of this now. 1:54 Okay, like we did with the first implementation of merge sort, 1:58 we're going to split the code up across three functions. 2:01 The main function merge sort, a split function, and a merge function. 2:05 Now if you were to look up a merge sort implementation in Python, both for 2:11 a regular list and array, or a linked list, you would find much more concise 2:15 versions out there, but they're kinda hard to explain. 2:19 So splitting it up into three will sort of help it be easier to understand. 2:22 So we'll call this merge_sort at the top level, and 2:27 this time it's going to take a linked_list. 2:30 Let's add a docked string to document the function. 2:34 So we'll say that this function sorts a linked list in ascending order. 2:37 And like before we'll add the steps in here, so 2:44 we'll say you first recursively divide the linked 2:49 list into sublists containing a single node. 2:54 Then we repeatedly merge these sublists 2:59 to produce sorted sublists until one remains. 3:05 And then finally, this function returns a sorted linked list. 3:11 The implementation of this top level merge function is nearly identical to 3:17 the array or list version we wrote earlier. 3:22 So first, we'll provide a stopping condition or two. 3:25 If the size of the list is one, or 3:28 it's an empty list, we'll return the link list since it's naively sorted. 3:30 So if linked_list.size, remember that function we wrote, 3:35 equal one, then we'll return linked_list. 3:41 elif linked_list.head Is None, meaning it's an empty list. 3:46 Then we'll return linked_list as well. 3:53 Okay, next, lets split the linked_list into a left and right half. 3:56 Conceptually, this is no different but 4:02 in practice we need to actually traverse the list. 4:05 We'll implement a helper method to make this easier. 4:08 We will say left_half, right_half = split(linked_list), 4:11 and once we have two sublists like before, 4:17 we can call merge_sort, the top level function on each. 4:20 So left = merge_sort(left_half). 4:26 And right = merge_sort on the right_half. 4:33 Finally, we'll merge these two top level sublists and return it, so 4:39 merge left and right. 4:43 Okay, nothing new here, but in the next video, let's implement the split logic. 4:45