Merge Two Sorted Arrays Efficient Code
In this class, We discuss Merge Two Sorted Arrays Efficient Code.
For Complete YouTube Video: Click Here
The reader should have basic programming knowledge. Click Here to learn Programming basics.
Take two sorted arrays a,b.
a is of size n, and b is of size m.
Merge two array elements to get the final sorted elements.
Example:
a = [1, 5, 7, 8]
b = [2, 4, 9]
Output:
a = [1,2, 4, 5]
b = [7, 8, 9]
We are not supposed to take extra space to do the sorting.
Time complexity = O(n+m)
Space complexity = O(1)
Watch our youtube video for coding intuition.
Code:
def merge(arr1,arr2,n,m):
maxnum=0
if(arr1[n-1]>arr2[m-1]):
maxnum=arr1[n-1]
else:
maxnum=arr2[m-1]
maxnum+=1
i=0
j=0
k=0
while(i<n and j<m and k<n+m):
num1=arr1[i]%maxnum
num2=arr2[j]%maxnum
if(num1<num2):
if(k<n):
arr1[k]+=num1*maxnum
else:
arr2[k-n]+=num1*maxnum
i+=1
k+=1
else:
if(k<n):
arr1[k]+=num2*maxnum
else:
arr2[k-n]+=num2*maxnum
j+=1
k+=1
while(i<n):
num1=arr1[i]%maxnum
if(k<n):
arr1[k]+=num1*maxnum
else:
arr2[k-n]+=num1*maxnum
i+=1
k+=1
while(j<m):
num2=arr2[j]%maxnum
if(k<n):
arr1[k]+=num2*maxnum
else:
arr2[k-n]+=num2*maxnum
j+=1
k+=1
for l in range(n):
arr1[l]//=maxnum
for l in range(m):
arr2[l]//=maxnum
n=int(input(“enter n value”))
m= int(input(“enter m value”))
arr1=[]
arr2=[]
print(“enter first array elements”)
for i in range(n):
x=int(input())
arr1.append(x)
print(“enter second array elements”)
for j in range(m):
x=int(input())
arr2.append(x)
merge(arr1, arr2, n, m)
for i in range(n):
print(arr1[i])
for j in range(m):
print(arr2[j])