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

1. If array1 have small number, store that and increment the index of count array1.
2. If the array2 have small number, store and increment the index count of array2.
3. When we reach the end of an array, print the elements of another array.
4. For example, if array1 is finished, store rest of elements of array2.

Program

#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]<<" ";
		}
	}
}

Alternative:

#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();
}