Merge Sort List in Python (Example)

In this Python article, you’ll learn how to use the merge sort algorithm to sort an integer list.

The page will consist of the following topics:

Let’s dive right in!

Creation of Example Data

First, let’s create a sample list for the following examples.

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

As shown, the_list contains seven negative and positive numbers.

Example: Implementing Merge Sort in Python

The following Python syntax shows how to define a function that sorts a list based on the merge sort algorithm, which utilizes the divide-and-conquer algorithmic paradigm. To be more specific, the entire list is divided into smaller lists. First, the sublists are sorted out. Then the sorted lists are merged to obtain a single sorted list. Let’s see how to implement it in Python!

First, the list length is checked to see if the list has a length of less than two. If that is the case, no operation is done, which the return command ensures.

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

After the check, if the list has two or more elements, the function divides the initial list into two sublists and then calls the merge_sort() function on them recursively. Once the function call ends and a sublist is returned, that sublist will be sorted. For example, after the line merge_sort(left_list), the sublist left_list will be sorted.

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 above commands, we now have two separate sorted sublists, left_list and right_list. The next step is to merge them and keep the elements ordered in the merged list.

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

The code segment above iteratively compares the elements from the two sublists and inserts the smaller element of the pair into the parent list lst. The process goes on until one of the sublists has no more elements to check. Finally, the remaining elements of the other list are added to the end of the parent list using the following script.

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

After the execution of the section above, the merging phase is complete, and the control is given away to the caller function, which will continue with the remaining subproblems. Here the caller function indicates, the merge_sort() execution which generated the merge_sort() execution for the sublist. Let’s run the code to sort our list as shown below!

merge_sort(the_list)                         # sorting the list
print("Printing the sorted array:", the_list)
# Printing the sorted array: [-14, -3.5, 1, 25, 31, 40, 856]

For the sake of clarity, we divided the code of the merge sort function into separate chunks above. Here is the complete code for your use below.

def merge_sort(lst):
    if len(lst) <= 1:
        return
 
    mid = len(lst)//2 # setting the middle index of the list
    left_lst = lst[:mid] # setting the left sublist
    right_lst = lst[mid:] # setting the right sublist
 
    merge_sort(left_lst) # sorting the left sublist
    merge_sort(right_lst) # sorting the right sublist
 
    # Now we have to merge the two subarrays and the resulting array should be sorted.
 
    i = 0
    j = 0
    x = 0
 
    while i < len(left_lst) and j < len(right_lst):
        if left_lst[i] < right_lst[j]:
            lst[x] = left_lst[i]
            i += 1
        else:
            lst[x] = right_lst[j]
            j += 1
        x += 1
 
    while i < len(left_lst):
        lst[x] = left_lst[i]
        i += 1
        x += 1
 
    while j < len(right_lst):
        lst[x] = right_lst[j]
        j += 1
        x += 1

I hope you found this explanation helpful. I highly recommend you visit the Visualization of Merge Sort in Python tutorial to gain further insight.

Video, Further Resources & Summary

Have a look at the following video on the Statistics Globe YouTube channel. I’m showing the content of this article in the video:

The YouTube video will be added soon.

Also, you could read the other tutorials on www.statisticsglobe.com. Some tutorials are 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

In this Python tutorial, you have learned how to sort an integer list with merge sort. If you have additional questions and/or comments, let me know in the comments section below.

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.