Monday, July 25, 2011

Merging two sorted arrays

Given two sorted arrays a[]={1,3,77,78,90} and b[]={2,5,79,81}. Merge these two arrays, no extra spaces are allowed. Output has to be a[]={1,2,3,5,77} and b[]={78,79,81,90}.

Algorithm: use two pointer & points l to 1st & r to 2nd array
if element in 1st is smaller than 2nd array element at index i then increment 1st pointer
else
swap element at index i in both array &b increment 1st pointer & sort 2nd
array its not necessary only if we need sorted output in each array
Solution:
size of a=m size of b =n
a[]={1,3,77,78,90} and b[]={2,5,79,81}
l r

No comments: