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,
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.