Merge two sorted array without duplicates

Question
Given two arrays, merge two sorted array without duplicates. Solve in a most efficient way.
Logic
- Compare first index element of both array and store the smaller one in the new array.
- Increment the index of array ( with a smaller number )
- Again compare elements of two array and store the least in new array.
Algorithm
- If array1 have small number, store that and increment the index of count array1.
- If the array2 have small number, store and increment the index count of array2.
- When we reach the end of an array, print the elements of another array.
- For example, if array1 is finished, store rest of elements of array2.
Program
[code lang=”c”]
#include<iostream.h>
#include<stdlib.h>
void main()
{
int *ar1,*ar2,*des,l,m,i,j,t=0;
cout<<"enter length of two arrays\n";
cin>>m>>l;
ar1 =(int*)malloc(l*sizeof(int)); // dynamic memory allocation based on the input
ar2 = (int*)malloc(m*sizeof(int));
des =(int*)malloc((l+m)*sizeof(int));
cout<<"enter first array elements";
for(i=0;i<l;i++)
cin>>ar1[i];
cout<<"enter second array elements";
for(i=0;i<m;i++)
cin>>ar2[i];
if(ar1[l-1]<ar2[0]) //if the last element of ar1 is lesser than first element of ar2
{
/* print ar1 first then ar2 */
for(i=0;i<l;i++)
cout<<ar1[i]<<" ";
for(j=0;j<m;j++)
cout<<ar2[j]<<" ";
}
else if( ar2[m-1]<ar1[0]) //if the first element of ar1 is greater than last of ar2
{
/* print ar2 first then ar1 */
for(j=0;j<m;j++)
cout<<ar2[j]<<" ";
for(i=0;i<l;i++)
cout<<ar1[i]<<" ";
}
else // merge only if both above condition fail
{
i=0;
j=0;
while(i<l&&j<m)
{
if(ar1[i]<ar2[j])
{
des[t]=ar1[i];
i++; //increment index of ar1, ar2 index unchanged
t++;
}
else if(ar2[j]<ar1[i])
{
des[t] =ar2[j];
j++; //increment index of ar2, ar1 index unchanged
t++;
}
else // both are equal
{
des[t] =ar1[i];
i++; // increment both index
j++;
t++;
}
}
while(i<l) // storing remaining of ar1
{
des[t]= ar1[i];
t++;
i++;
}
while(j<m) //storing remaining of ar2
{
des[t] =ar2[j];
t++;
j++;
}
for(i=0;i<t;i++) //merged array
{
cout<<des[i]<<" ";
}
}
}
[/code]
Alternative:
[code lang=”c”]
#include<stdio.h>
void main()
{
int a[20],b[20],i,j,m,n,k,l=1;
clrscr();
printf("enter the first array size:");
scanf("%d",&m);
printf("enter the first array values:");
for(i=0;i<m;i++)
{
scanf("%d",&a[i]);
}
printf("enter the second array size:");
scanf("%d",&n);
printf("enter the second array values :");
for(i=0;i<n;i++)
{
scanf("%d",&b[i]);
}
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(b[i]==a[j]) //two numbers are equal then do nothing
{
l=0;
break;
}
else if(b[i]<a[j]) //larger element found
{
l=0;
for(k=m;k>j;k–) //swap the elements to insert b[i]
{
a[k]=a[k-1];
}
m++; //increments the length of destination array
a[j]=b[i]; //insert b[j] into a[]
break;
}
}
if(l==1) //all elements in b[] is greater than last element b[]
{
a[m]=b[i];
m++;
}l=1; //act as a marker
}
for(i=0;i<m;i++) //prints the destination array
{
printf("%d ",a[i]);
}
getch();
}
[/code]