Merge Sort8:07 with Pasan Premaratne
Before we implement merge sort in code lets understand how it works conceptually.
[MUSIC] 0:00 Now that we've seen two different data structures, let's circle back and 0:04 apply what we know about algorithms to these new concepts. 0:08 One of the first algorithms you learned about was binary search. 0:11 And we learned that with binary search there was one pre-condition. 0:14 The data collection needs to be sorted. 0:18 Over the next few videos let's implement the merge sort algorithm, 0:20 which is one of many sorting algorithms on both arrays or Python lists and 0:23 the singly linked list we just created. 0:28 This way we can learn a new sorting algorithm that has real world use cases 0:30 and see how a single algorithm can be implemented on different data structures. 0:35 Before we get into code, let's take a look at how merge sort works conceptually, 0:40 and we'll use an array to work through this. 0:45 We start with an unsorted array of integers, and 0:48 our goal is to end up with an array sorted in ascending order. 0:51 Merge Sort works like binary sort by splitting up the problem into 0:55 sub-problems, but it takes the process one step further. 0:59 On the first pass, we're going to split the array into two smaller arrays. 1:03 Now in binary search, one of these subarrays would be discarded. 1:07 But that's not what happens here. 1:11 On the second pass, we're going to split each of those subarrays into further, 1:12 smaller, evenly sized arrays. 1:17 And we're going to keep doing this until we're down to single element arrays. 1:19 After that, the Merge Sort algorithm works backwards, 1:23 repeatedly merging the single element arrays, and sorting them at the same time. 1:27 Since we start at the bottom, by merging two single element arrays, 1:32 we only need to make a single comparison to sort the resulting merged array. 1:37 By starting with smaller arrays that are sorted as they grow, Merge Sort has 1:42 to execute fewer sort operations than if it sorted the entire array at once. 1:47 Solving a problem like this by recursively breaking down the problem into 1:52 subparts until it is easily solved is an algorithmic strategy known as divide and 1:56 conquer. 2:01 But instead of talking about all of this in the abstract, let's dive into the code. 2:02 This way, we can analyze the run time as we implement it. 2:06 For our first implementation of Merge Sort, we're going to use an array, or 2:10 a Python list. 2:15 While the implementation won't be different conceptually for a linked list, 2:16 we will have to write more code because of list traversal and how nodes are arranged. 2:20 So once we have these concepts squared away, we'll come back to that. 2:25 Let's add a new file here. 2:29 We'll call this merge_sort.py. 2:33 In our file let's create a new function named merge_sort that takes a list. 2:38 And remember when I say list, unless I specify linked list, 2:43 I mean a Python list which is the equivalent of an array. 2:47 So we'll say def merge_sort that takes a list. 2:51 In the Introduction to Algorithms course, we started our study of each algorithm 2:57 by defining the specific steps that comprise the algorithm. 3:02 Let's write that out as a doc string in here, 3:05 the steps of the algorithm so that we can refer to it right in our code. 3:09 This algorithm is going to sort the given list in an ascending order. 3:14 So we'll start by putting that in here as a simple definition. 3:18 Sorts a list in ascending order. 3:22 There are many variations of merge_sort, and 3:27 in the one we're going to implement, we'll create and return a new sorted list. 3:30 Other implementations will sort the list we pass in, and 3:35 this is less typical, in an operation known as sort in place. 3:39 But I think that returning a new list makes it easier to understand the code. 3:43 Now, these choices do have implications though, and 3:48 we'll talk about them as we write this code. 3:50 For our next bit of the doc string, let's write down the output of this algorithm. 3:53 So it returns a new sorted list. 3:58 Merge_sort has three main steps. 4:02 The first is the divide step, where we find the midpoint of the list. 4:06 So I'll say, Divide: Find the midpoint 4:10 of the list and divide into sublists. 4:17 The second step is the Conquer step where we sort the sublists that we created in 4:22 the Divide step. 4:27 So we'll say, recursively sort the sublists created in previous step. 4:28 And finally, the Combine step where we 4:36 merge these recursively sorted sublists back into a single list. 4:39 So merge the sorted sublists created in previous step. 4:44 When we learned about algorithms, 4:53 we learned that a recursive function has a basic pattern. 4:55 First, we start with a base case that includes a stopping condition. 4:59 After that we have some logic that breaks down the problem and 5:04 recursively calls itself. 5:07 Our stopping condition is our end goal, a sorted array. 5:09 Now, to come up with a stopping condition or a base case, 5:14 we need to come up with the simplest condition that satisfies this end result. 5:17 So there are two possible values that fit, a single element list or an empty list. 5:23 Now, in both of these situations, we don't have any work to do. 5:29 If we give the merge_sort function an empty list or 5:33 a list with one element, it's technically already sorted. 5:36 We call this naively sorting. 5:39 So let's add that as our stopping condition. 5:42 We'll say if len(list), if the length of the list, 5:46 is <=1, then we can return the list. 5:50 Okay, so this is a stopping condition. 5:53 And now that we have a stopping condition, we can proceed with the list of steps. 5:56 First, we need to divide the list into sublists. 6:02 To make our functions easier to understand, we're going to put our logic 6:06 in a couple different functions instead of one large one. 6:10 So I'll say, left_half, 6:13 right_half = split(list). 6:18 So here we're calling a split function that splits the list we pass in and 6:23 returns two lists split at the midpoint. 6:28 Because we're returning two lists, we can capture them in two variables. 6:31 Now, you should know that this split function is not something that comes 6:35 built into Python. 6:39 This is a global function that we're about to write. 6:40 Next is the Conquer step where we sort each sublist and 6:43 return a new sorted sublist. 6:48 So we'll say left = merge_sort(left_half), 6:50 And right = merge_sort(right_half). 6:58 This is the recursive portion of our function. 7:04 So here we're calling merge_sort on this divided sublist. 7:07 So we divide the list into two here and then we call merge_sort on it again. 7:11 This further splits that sublist into two. 7:15 In the next passthrough of merge_sort, this is going to be called again and 7:19 again and again, until we reach our stopping condition where we have single 7:24 element lists or empty lists. 7:29 When we've subdivided until we cannot divide anymore, 7:31 then we'll end up with a left and a right half, and we can start merging backwards. 7:35 So let's say, return merge(left, right). 7:41 That brings us to the Combine step. 7:46 Once two sublists are sorted and combined, we can return it. 7:49 Now, obviously none of these functions, merge, merge_sort, 7:54 well merge_ort is written, but merge and split haven't been written. 7:57 So all we're going to do here, if we run it is raise in error. 8:00 So in the next video let's implement the split operation. 8:04
You need to sign up for Treehouse in order to download course files.Sign up