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:

Also, you could read the other tutorials on www.statisticsglobe.com. Some tutorials are listed below.

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.

Subscribe to the Statistics Globe Newsletter