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/
Ajitesh Shukla
Latest posts by Ajitesh Shukla (see all)
- How to sort elements using Merge sort in python - February 14, 2018
- How to easily print triangle patterns in python - February 7, 2018
