How to Implement Merge Sort Using Recursion?

def merge(list_a, list_b):
def merge(list_a, list_b):list_sorted = []
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. def merge(list_a, list_b):list_sorted = []while list_a != [] and list_b != []:
def merge(list_a, list_b):list_sorted = []while list_a != [] and list_b != []:if list_a[0] < list_b[0]:
list_a
is the smaller of the two values, then we can pop
it out of the list and into list_sorted
. def merge(list_a, list_b):list_sorted = []while list_a != [] and list_b != []:if list_a[0] > list_b[0]:list_sorted.append(list_a.pop(0))
list_b
and into list_sorted
instead. def merge(list_a, list_b):list_sorted = []while list_a != [] and list_b != []:if list_a[0] > list_b[0]:list_sorted.append(list_a.pop(0))else:list_sorted.append(list_b.pop(0))
list_sorted
, and then list_sorted
can be returned. def merge(list_a, list_b):list_sorted = []while list_a != [] and list_b != []:if list_a[0] < list_b[0]:list_sorted.append(list_a.pop(0))else:list_sorted.append(list_b.pop(0))if len(list_a) < 1:list_sorted += list_belse:list_sorted += list_areturn list_sorted
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. def merge_sort(unsorted):if len(unsorted) <= 1:return unsorted
def merge_sort(unsorted):if len(unsorted) <= 1:return unsortedelse:middle = int(len(unsorted)) / 2 # rounding down if the list has an odd number of items
front = unsorted[:middle]back = unsorted[middle:]
merge_sort
function is used again, this time on these split lists. def merge_sort(unsorted):if len(unsorted) <= 1:return unsortedelse:middle = int(len(unsorted) / 2)front = merge_sort(unsorted[:middle])back = merge_sort(unsorted[middle:])
merge
function you have already written. def merge_sort(unsorted):if len(unsorted) <= 1:return unsortedelse:middle = int(len(unsorted) / 2)front = merge_sort(unsorted[:middle])back = merge_sort(unsorted[middle:])return merge(front, back)
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. def merge(list_a, list_b):list_c = []while len(list_a) > 0 and len(list_b) > 0:if list_a[0] < list_b[0]:list_c.append(list_a.pop(0))else:list_c.append(list_b.pop(0))if list_a == []:list_c += list_belse:list_c += list_aprint("merged list is", list_c)return list_cdef merge_sort(unsorted):if len(unsorted) < 2:return unsortedelse:middle = len(unsorted) // 2front = unsorted[:middle]back = unsorted[middle:]print("splits are", front, back)front = merge_sort(front)back = merge_sort(back)return merge(front, back)my_list = [5,4,3,2,1]
merge_sort(my_list)
splits are [5, 4] [3, 2, 1]
splits are [5] [4]
merged list is [4, 5]
splits are [3] [2, 1]
splits are [2] [1]
merged list is [1, 2]
merged list is [1, 2, 3]
merged list is [1, 2, 3, 4, 5]
Programming 102: Think Like a Computer Scientist

Our purpose is to transform access to education.
We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.
We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.
You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.
Learn more about how FutureLearn is transforming access to education