Merge sort explained - python coding

Published at - Sep 14, 2021

In computer science, merge sort is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output.

Some important points

• Based on Divide and conquer strategy
• Requires extra space to hold the two halves

Time & Space Complexity

Worst complexityn*log(n)
Average complexityn*log(n)
Best complexityn*log(n)
Space complexityn

Algorithm

MergeSort(arr[], l, r)

If r > l

Find the middle point to divide the array into two halves: middle m = l+ (r-l)/2
Call mergeSort for first half: Call mergeSort(arr, l, m)
Call mergeSort for second half: Call mergeSort(arr, m+1, r)
Merge the two halves sorted in step 2 and 3: Call merge(arr, l, m, r)

Python program for implementation of MergeSort

def mergeSort(arr):
if len(arr) >1:
mid = len(arr)//2 # Finding the mid of the array
L = arr[:mid] # Dividing the array elements
R = arr[mid:] # into 2 halves

mergeSort(L) # Sorting the first half
mergeSort(R) # Sorting the second half

i = j = k = 0

# Copy data to temp arrays L[] and R[]
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i+= 1
else:
arr[k] = R[j]
j+= 1
k+= 1

# Checking if any element was left
while i < len(L):
arr[k] = L[i]
i+= 1
k+= 1

while j < len(R):
arr[k] = R[j]
j+= 1
k+= 1

# Code to print the list
def printList(arr):
for i in range(len(arr)):
print(arr[i], end =" ")
print()

# driver code to test the above code
if __name__ == '__main__':
arr = [12, 11, 13, 5, 6, 7]
print ("Given array is", end ="\n")
printList(arr)
mergeSort(arr)
print("Sorted array is: ", end ="\n")
printList(arr)

All programs will print sorted array as output.

Thank You!

Harendra Kanojiya

Hello, I am Harendra Kumar Kanojiya - Owner of this website and a Fullstack web developer. I have expertise in full-stack web development using Angular, PHP, Node JS, Python, Laravel, Codeigniter and, Other web technologies. I also love to write blogs on the latest web technology to keep me and others updated. Thank you for reading the articles.

Related Posts -

Selection sort examples in ...

In this lesson on python coding, we will talk about one of the fundamen...

Bubble sort examples in pyt ...

In this lesson on python coding, we will talk about one of the fundamental ...