OneCompiler

merge sort

137

def merge1(arr,l,m,r):
n1=m-l+1
n2=r-m

L=[0](n1)
R=[0]
(n2)

for i in range(0,n1):
L[i]=arr[l+i]
for j in range(0,n2):
R[j]=arr[m+1+j]

i=0
j=0
k=l

while i<n1 and j<n2:
if L[i]<= R[j]:
arr[k]=L[i]
i+=1
else:
arr[k]=R[j]
j+=1
k+=1

while i<n1:
arr[k]=L[i]
i+=1
k+=1
while j<n2:
arr[k]=R[j]
j+=1
k+=1

def mergesort1(arr,l,r):
if l<r:
m=l+(r-l)//2
mergesort1(arr,l,m)
mergesort1(arr,m+1,r)
merge1(arr,l,m,r)

arr=[10,65,8,5,3]
num=len(arr)
print("Given array: ")
for i in range(num):
print("%d"%arr[i],end=" ")
mergesort1(arr,0,num-1)
print("\n\nSorted array: ")
for i in range(num):
print("%d"%arr[i],end=" ")