Merge Sort in Python

MERGE SORT IN PYTHON

Hello learners, Welcome back to yet another article on Merge sort in Python. In this article, we are going to learn about

• python merge sort and its implementation.

​So let’s get started... 

---

 

🧐🤷‍♀️What is the Merge sort Algorithm?

Merge sort is an efficient Divide and Conquer algorithm. It uses the concept of dividing the array into two halves and then calls itself for the two halves and then after merging the two halves after sorting the arrays.

 

To get a clear idea about how merge sort works looks at the example shown below in picture:

image merge sort

 

💻MERGE SORT CODE IN DESCENDING ORDER IN PYTHON:

Given below is a merge sort in python program or python merge sort program:

def mergesort(a,p,r):
    if(p<r):
        q=(p+r)//2
        mergesort(a,p,q)
        mergesort(a,q+1,r)
        merge(a,p,q,r)
def merge(a,x,y,z):
    n1=y-x+1
    n2=z-y
    L=[]
    R=[]
    for i in range(n1):
        L.append(a[x+i])
    for j in range(n2):
        R.append(a[y+j+1])
    i=j=0
    L.append("Z")
    R.append("Z")
    for k in range(x,z+1):
        if((L[i])>=(R[j])):
            a[k]=L[i]
            i+=1
        else:
            a[k]=R[j]
            j+=1
a=['s','b','t','a','e','f','g','h','i','j']
length=len(a)
print("Before sorting=",a)
mergesort(a,0,length-1)
print("After sorting=",a)

Output

Before sorting= ['s', 'b', 't', 'a', 'e', 'f', 'g', 'h', 'i', 'j']

After sorting= ['t', 's', 'j', 'i', 'h', 'g', 'f', 'e', 'b', 'a']

This python merge sort algorithm sorts the data in descending order.

 

📌Time Complexity:

Overall time complexity of python Merge sort is given by: O(nlogn).

 

🧐Space Complexity:

Python merge sort program requires an auxiliary space of O(n).

 

That's all in this article - merge sort in python. Meet you in next articles with some more programming concepts.