How to sort elements using Merge sort in python

Merge Sort:

Merge sort is the efficient algorithm of sorting the elements of the array in either ascending order or descending order because it has complexity O(n log(n)). We can easily implement merge sort using recursion.

In Merge sort, we divide the array into two half array till we get the array of elements separately and then by comparing the elements accordingly, we merge the elements again to form a sorted array.


In python, the code of merge-sort contains two functions-

  • Merge Function:

This function is used to merge two arrays to form a single array. It takes two arrays as the arguments. In this function, we take two arrays and merge them by comparing their values in ascending order. It stores the merged array in another array and at the end, it returns it. It uses simple concepts of branching and looping. The function of each branching condition is shown in the code. The code for this function is:

def merge(A,B):
    c=[]
    m=len(A)
    n=len(B)
    (i,j)=(0,0) #initialising i=0 and j=0
    while(i+j<m+n): #till i and j travese every element of both lists
        if(i==m): #if first array is empty
            c.append(B[j])
            j=j+1
        elif(j==n): #if second array is empty
            c.append(A[i])
            i=i+1
        elif(A[i]<=B[j]): #if element at i position in A is less than element at j position in B
            c.append(A[i])
            i+=1
        elif(A[i]>=B[j]): #if element at i position in A is greater than element at j position in B
            c.append(B[j])
            j=j+1   
    return(c)
  • Mergesort function:



This function takes three arguments one is array,  other is starting index of the array to sort from and third is ending index of the array till which the array is to be sort.The code for this function is:

def mergesort(A,left,right):
    if(right-left<=1):
        
        return(A[left:right])
        
    if(right-left>1):
        mid=(left+right)//2
        L=mergesort(A,left,mid)
        R=mergesort(A,mid,right)
        
        return(merge(L,R))



Code:

def merge(A,B):
    c=[]
    m=len(A)
    n=len(B)
    (i,j)=(0,0)
    while(i+j<m+n):
        if(i==m):
            c.append(B[j])
            j=j+1
        elif(j==n):
            c.append(A[i])
            i=i+1
        elif(A[i]<=B[j]):
            c.append(A[i])
            i+=1
        elif(A[i]>=B[j]):
            c.append(B[j])
            j=j+1   
    return(c)    


def mergesort(A,left,right):
    if(right-left<=1):
        
        return(A[left:right])
        
    if(right-left>1):
        mid=(left+right)//2
        L=mergesort(A,left,mid)
        R=mergesort(A,mid,right)
        
        return(merge(L,R))

q=[1,9002,299029302,3,9,6,55,2,53,0]

print(mergesort(q,0,10))


OUTPUT:



For more python examples click on the link below:

http://spiderlabweb.com/python-programs/

The following two tabs change content below.
Ajitesh Shukla

Ajitesh Shukla

Tech Expert at SpiderLabWeb
Extremely diligent about new technology and their working. Loves to work on OS development and Internet of Things. Also,interested in competitive coding.
Ajitesh Shukla

Latest posts by Ajitesh Shukla (see all)

You may also like...