Introduction to Merge Sort in Python
The term “merge sort” refers to a general-purpose sorting algorithm in Python that divides a list into sub-lists with a maximum of one element in each sub-list before merging the sub-lists in reverse order to produce the sorted sub-lists. Merge sort is then used to refer to a single list that has undergone sorting. The total, average, and worst-case time complexity of this effective, versatile, and best sorting method are
O(nlogn).
The logic behind Merge Sort in Python
An unsorted list of “n” integers broken into sub-lists until each sub-list has only one element will be provided to us for the merge sort. Hence, we’ll split the list into n sub-lists, each of which will have a single element that will be sorted independently. To create sorted sub-lists and a final sorted sub-list, we will now combine all the sub-lists.
Logic: (Divide and Conquer) (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.
The task at hand is to split the supplied list in half and use the divided and conquer technique to sort it as a merge sort.
Let’s say that a given list has five items. We may split the list into two sublists of two elements each by computing mid (start+end/2), which in this case is 2.5, and taking into account integer component 2. Nevertheless, two sublists are insufficient to solve the issue.
The sub-problems will be further divided until each sub-list only has one element, at which point all of the sub-lists will be combined to create a sorted sub-list, and lastly, a sorted list.
Consider a list having the components 12 5 9 2 10. We will now divide and merge the list step by step as follows: The first step is 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
The issue has been broken down into smaller problems in each step up to this point, until step 4, when each smaller problem has only one ingredient.
To arrive at the whole answer, we will now combine the solutions to all of the subproblems. Step 5: 5 12 9 | 2 10 Step 6: 5 9 12 | 2 10 Step 7: 2 5 9 10 12
It is clear from the preceding stages that we split a list of size N into N/2 sub-lists at each stage until we are unable to divide further.
Using the guidelines below, we implement the merge sort.
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
The examples are shown below.
mentioned:
Example #1
The merge sort is implemented using a recursive method.
def mergeSort(ar_list): Results:
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)
Example #2
Python implementation of merge sort using bottom-up methodology is shown below. Code:
def merge(left, right): Results:
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))
