Updated March 28, 2023
Introduction to Merge Sort in Python
In python, merge sort is defined as one of the sorting algorithms which is general-purpose, uses comparison based sorting by divide and conquer algorithm where the idea is to break down the list into sub-lists until each sub-list has max one element and merge all the sub-lists in reverse order to get the sorted sub-lists and finally a single list which is sorted is called merge sort. It is an efficient, general-purpose, and best sorting algorithm with the overall, average, and worst-case time complexity being O(nlogn).
The logic behind Merge Sort in Python
In the merge sort, we will be given an unsorted list of ‘n’ numbers divided into sub-lists until each sub-list has only one element. So we will divide the list into n sub-lists having one element, which is sorted by itself. Now we will merge all the sub-lists to get sorted sub-lists and finally a sorted sub-list.
Logic: (Divide and Conquer)
- We will divide the problem into multiple subproblems.
- We will solve the sub-problems by further dividing the sub-problems into atomic problems where they have an exact solution.
- Finally, we will combine all sub solutions to get the final solution to the given problem.
Here the problem is to sort a given list as merge sort followed as divided and conquer method; we will divide the given list to mid of the list.
Let us consider, given list has five elements, now we will divide the list to its midway by calculating mid (start+end/2), here it is 2.5, and we will consider integer part 2, so one sub-list has 2 elements and another sub-list has 3 elements, but 2 sub-lists are not enough to solve the problem.
We will divide the sub-problems further until it has one element in each sub-list as atomic problems, and finally, we will merge all sub-list to form a sorted sub-list and finally a sorted list.
Let us consider a list with elements 12 5 9 2 10; now, we will have step by step dividing and merging as follows:
Step 1: 12 5 9 2 10 (mid = 5/2 = 2)
Step 2: 12 5 9 | 2 10
Step 3: 12 5 9 | 2 10
Step 4: 12 5 9 | 2 10
Till now, in all steps, we are dividing the problem into subproblems until each subproblem has only one element, as in step 4.
Now we will merge all the subproblems with a solution to get the final solution.
Step 5: 5 12 9 | 2 10
Step 6: 5 9 12 | 2 10
Step 7: 2 5 9 10 12
From all the steps in the above, one can find out that at each step, we are dividing a list of size N to N/2 sub-lists until we cannot divide further.
In the merge sort implementation, we follow the below steps:
- We will take two variables, “start” and “end”, where “start” will store the starting index, i.e. 0 in it, and the end will store the length of the list, i.e. 5 in the above example.
- Using start and end variables, we will find the middle of the list by using the formula as (start+end)/2 and store the result in variable mid, and we will divide the list into 2 sub-lists as a start to mid as one sub-list and mid+1 to end as another sub-list.
- We will divide the sub-lists into further sub-lists as atomic problems by following the process in step 2.
- Finally, we will merge all sub-lists with solutions to get the final list that will be in sorted order.
Examples of Merge Sort in Python
Given below are the examples mentioned:
Example #1
The recursive approach of implementing the merge sort
Code:
def mergeSort(ar_list):
if len(ar_list) > 1:
mid = len(ar_list) // 2
left = ar_list[:mid]
right = ar_list[mid:]
# Recursive call on each half
mergeSort(left)
mergeSort(right)
# Two iterators for traversing the left and right half
i = 0
j = 0
# Iterator for the main list
k = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
# The value from the left half has been used
ar_list[k] = left[i]
# Move the iterator forward
i += 1
else:
ar_list[k] = right[j]
j += 1
k += 1
# For all the remaining values
while i < len(left):
ar_list[k] = left[i]
i += 1
k +=1
while j < len(right):
ar_list[k]=right[j]
j += 1
k += 1
ar_list = [12, 7, 2, 9, 4, 15, 5]
mergeSort(ar_list)
print(ar_list)
Output:
Example #2
Bottom-up approach implementation of merge sort in python as below.
Code:
def merge(left, right):
result = []
x, y = 0, 0
for k in range(0, len(left) + len(right)):
if x == len(left): # if at the end of 1st half,
result.append(right[y]) # add all values of 2nd half
y += 1
elif y == len(right): # if at the end of 2nd half,
result.append(left[x]) # add all values of 1st half
x += 1
elif right[y] < left[x]:
result.append(right[y])
y += 1
else:
result.append(left[x])
x += 1
return result
def mergesort(ar_list):
length = len(ar_list)
size = 1
while size < length:
size+=size # initializes at 2 as described
for pos in range(0, length, size):
start = pos
mid = pos + int(size / 2)
end = pos + size
left = ar_list[ start : mid ]
right = ar_list[ mid : end ]
ar_list[start:end] = merge(left, right)
return ar_list
ar_list = [33, 42, 9, 37, 8,47, 5]
print(mergesort(ar_list))
Output:
Conclusion
Finally, it’s all about the merge sort in python. So far, we have discussed the definition of merge sort, what are the logic behind the merge sort implementation and the explanation of the logic, different types of implementations of merge sort in python with examples and corresponding outputs. Here you will have a clear and good understanding of the merge sort and easily solve the merge sort problems.
Recommended Articles
This is a guide to Merge Sort in Python. Here we discuss the introduction, logic behind merge sort in python and examples. You may also have a look at the following articles to learn more –
