How to Implement Merge Sort Using Recursion

In this article, we will create a couple of functions which will work together to perform a merge sort. A key aspect of the merge sort algorithm is the ability to merge two sorted lists into a single sorted list. We can start by creating a function to do just this. Within this function, let’s create an empty list, into which the two other lists will be merged.  Now we’re going to start comparing the heads (the initial items) of list_a and list_b, and moving the smallest value into list_sorted. We want to keep doing this until both lists are empty. So for example, given these lists: 

list_a = [3,7,8]
list_b = [2,4,9]
list_sorted = []

 The first time around, we would want the function to compare the values 3 and 2. As 2 is smaller, it gets moved into list_sorted, so the lists will now look like this: 

list_a = [3,7,8]
list_b = [4,9]
list_sorted = [2]

 Then 3 and 4 are compared, and 3 is smaller so it is appended to list_sorted: 

list_a = [7,8]
list_b = [4,9]
list_sorted = [2,3]

 This is repeated until either of the lists is empty. How will we implement this? Let’s start with a loop, checking that both loops are not empty.  Now compare the heads of each list:  If the item in list_a is the smaller of the two values, then we can pop it out of the list and into list_sorted.  If the item is larger, then we need to pop the item out of list_b and into list_sorted instead.  If one of the lists becomes empty, then what remains in the other list (which is already sorted) can be added to the end of list_sorted, and then list_sorted can be returned.  Let’s try out the merge function. Run your code, and then pass the function a couple of sorted lists. 

>>> merge([3,7,8],[2,4,9])
[2, 3, 4, 7, 8, 9]
>>>

 Now that we can merge lists together, let’s tackle the other part of the algorithm. We need to split the large unsorted list into two, then do the same again and again and again, until we have a bunch of lists each with only one item. Then we can use the merge function to keep combining the lists together. So for the following list, it would look like this: 

[4,7,3,1,9,3,1]/ \
[4,7,3][1,9,3,1]/ \ / \
[4][7,3][1,9][3,1]/ / \ / \ / \
[4][7][3][1][9][3][1]

 Whenever you face a problem in programming where the solution seems to break down into smaller and repeating tasks, it’s probably a good idea to use a recursive strategy. Recursion is when a function is called by itself! Let’s have a look at how this works. We start with what is called the base case. this is when the algorithm will come to an end.  So here we are returning any list that is either empty or contains only one item, as by definition these lists must be sorted. In all other cases there are at least two elements in the list, so next we want to split the list into two smaller lists. To do this, we can find the middle point in the list and then take slices from the first element up to the middle, and the middle element to the end.  Now the lists have been split. Next they need splitting again, unless they are only one item long. So the merge_sort function is used again, this time on these split lists.  This will keep splitting the lists until each list is either one or zero items in length. At this point you want to merge the lists back together, and to do this you can use the merge function you have already written.  This function returns a sorted list each time it is called. This may result in additional calls of the merge_sort function with parts of the list. Each call of the function returns a sorted list until the uppermost one is complete. For example, where the merge_sort function is called in the line front = merge_sort(unsorted[:middle]), then several other calls are made until eventually a sorted list is returned and stored in the front variable. The function would then move onto running a merge sort on the second half of the longer list. So to summarise, this function keeps splitting a list until there are a set of lists each 1 or 0 items in size. It then repeatedly merges those lists together, but in order. If you want to try and get a clearer picture of what the code is doing, then it’s worth adding a few print statements. Here’s a slightly edited version of the merge sort program that you can use. You might notice the introduction of the // operator, this is known as floor division and carries out the division but only retains the integer part. This is functionally the same as int(len(unsorted) / 2), just shorter.  The output show the order in which lists are split into sublists and then merged. You should get something like the following: