Recursive Merge Sort in Python (Example)

In this tutorial, I’ll show how to implement a recursive merge sort algorithm in the Python programming language.

The page will consist of the following topics:

Let’s dive right in!

Creation of Example Data

First, we should create a sample list to be used in the following examples.

the_list = [-14, 25, 31, 40, -3.5, 856, 1]

As shown, the_list contains seven negative and positive numerals.

Example: Implementation of Merge Sort in Python

The following Python syntax defines a function that sorts a list based on the merge sort algorithm. The function will divide the initial list into two sublists and then recall itself on them. Thus, the function will be recursively called on the sublists and their sublists. To prevent an infinite loop, a stopping condition will be set to stop the call when the lists are either empty or in size of one. Let’s see the details of the process step by step!

First, to prevent any other unnecessary operation, the merge_sort function checks if the stopping condition is met.

def merge_sort(lst):
    if len(lst) <= 1:                         # checking the list length
       print(lst)
       return

If the list passes the check, it is split into two sublists, and the function merge_sort() is recalled on them.

mid = len(lst)//2                            # setting the middle index of the array
left_list = arr[:mid]                        # setting the left subarray
right_list = arr[mid:]                       # setting the right subarray
 
merge_sort(left_list)                        # sorting the left subarray
merge_sort(right_list)                       # sorting the right subarray

After the execution of the commands above, two sorted sublists left_list and right_list are obtained. In the next step, these two lists are merged, preserving the order of the elements.

Below, we see the merging phase of the function, where the sorted sublists left_list and right_list are compared elementwise, and the parent list is filled in an increasing ordering.

i = 0                                        # initializing some loop variables
j = 0
x = 0
 
while i < len(left_list) and j < len(right_list):
    if left_list[i] < right_list[j]:         # finding the current smallest element
        lst[x] = left_list[i]                # assigning the element to the parent list
        i += 1                               # incrementing left list index
    else:
        lst[x] = right_list[j]               # assigning the element to the parent list
        j += 1                               # incrementing right list index
    x += 1                                   # incrementing parent list index

Once one of the sublists runs out of elements, the while loop above terminates, and the following while loop below is executed for the sublist that still includes some elements. The command ensures that the remaining elements of the non-empty sublist are directly added to the parent list. When the merging is complete, the control is given to the caller function, which will continue with the remaining subproblems.

while i < len(left_list):                    # checking if left list has more elements
    lst[x] = left_list[i]                    # assigning the element to the parent list
    i += 1                                   # incrementing left list index
    x += 1                                   # incrementing parent list index
 
while j < len(right_list):                   # checking if right list has more elements
    lst[x] = right_list[j]                   # assigning the element to the parent list
    j += 1                                   # incrementing right list index
    x += 1                                   # incrementing parent list index
 
print(lst) # printing the current list

The execution of the function is shown below for the sample list the_list. You can see how the steps of the recursive calls have been taken.

merge_sort(the_list)                        # sorting the list
# [-14]
# [25]
# [31]
# [25, 31]
# [-14, 25, 31]
# [40]
# [-3.5]
# [-3.5, 40]
# [856]
# [1]
# [1, 856]
# [-3.5, 1, 40, 856]
# [-14, -3.5, 1, 25, 31, 40, 856]

• First, [-14, 25, 31, 40, -3.5, 856, 1] is separated into the lists [-14, 25, 31] and [40, -3.5, 856, 1] with respect to the middle of the list mid=7//2=3. Following this, the function is recalled for [-14, 25, 31]. The list is divided into two parts [-14], [25,31] once again with respect to mid=3//2=1. Then the function is recalled for [-14]. Since this sublist only consists of -14, no action is made on it. The element is printed, and the execution is returned to the parent function call. Here parent function call describes the function process, which calls the function with a sublist. See the first line of the output above.

•The execution restarts for [25,31]. The sublist is divided into [25] and [31], see the second and third lines of the given output.

•The merging phase takes place for [25] and [31] for the first time. As a result, [25,31] will be formed since the list is initially in the correct ordering, see the fourth line of the previous output.

• The list [25,31] is merged with [-14] to form [-14, 25, 31], see the fifth line.

• The same steps will be taken for the list [40, -3.5, 856, 1] as well. Once it is sorted like [-3.5, 1, 40, 856], it will be merged with the previously sorted list [-14, 25, 31], see from the 6th to 13th line shown in the output.

This is the end of the recursive merge-sort algorithm tutorial. I hope you found it helpful, see you at the next one!

Video & Further Resources

I have recently published a video on my YouTube channel, which shows the Python syntax of this post. You can find the video below:

The YouTube video will be added soon.

In addition, you could have a look at the other Python programming tutorials on my homepage. A selection of articles is listed below.

• k-way Merge Sort in Python
• Visualization of Merge Sort in Python
• Pseudocode for Merge Sort in Python
• Function & Library for Merge Sort in Python
• Python Programming Language

To summarize: This tutorial illustrated how to apply a recursive merge sort algorithm on a list in Python. Let me know in the comments below if you have additional questions.

This page was created in collaboration with Ömer Ekiz. Have a look at Ömer’s author page to get more information about his professional background, a list of all his tutorials, as well as an overview of his other tasks on Statistics Globe.