12. Merge 2 sorted arrays.
12. Merge 2 sorted arrays.
Problem link :- click here
C code
//merge two sorted arrays
#include<stdio.h>
void merge(int a[], int b[], int m, int n)
{
int i, j; //i->b j->a
int last;
for(i=n; i>=0; i--)
{
j = m-2;
last = a[j];
for(j=m-2; j>=0 && b[i]<a[j]; j--)
{
a[j+1] = a[j];
}
if(j!=m-2 || last>b[i])
{
a[j+1] = b[i];
b[i] = last;
}
}
}
void main()
{
int arr1[30], arr2[30];
int m, n;
int i;
printf("Enter the size of the array 1\n");
scanf("%d",&m);
printf("Enter the elements of the array 1\n");
for(i=0; i<m; i++)
scanf("%d",&arr1[i]);
printf("Enter the size of the array 2\n");
scanf("%d",&n);
printf("Enter the elements of the array 2\n");
for(i=0; i<n; i++)
scanf("%d",&arr2[i]);
printf("Array 1:-\n");
for(i=0; i<m; i++)
printf("\t%d",arr1[i]);
printf("\n");
printf("Array 2:-\n");
for(i=0; i<n; i++)
printf("\t%d",arr2[i]);
printf("\n");
merge(arr1, arr2, m, n);
printf("\n\nArray after merging :- \n");
for(i=0; i<m; i++)
printf("\t%d",arr1[i]);\
for(i=0; i<n; i++)
printf("\t%d",arr2[i]);
printf("\n\n");
}
Java code
//Merge 2 sorted arrays
package programs;
import java.util.Scanner;
public class Array__12
{
static void merge(int a[], int b[], int m, int n)
{
int i, j, last;
i = n-1; //this is for b
j = m-2;
for(i=n-1; i>=0; i--)
{
last = a[m-1];
for(j=m-2; j>=0 && a[j]>b[i]; j--)
a[j+1] = a[j];
if(j == -1)
{
a[0] = b[i];
b[i] = last;
}
else if(b[i]>=a[j] && b[i]<last)
{
a[j+1] = b[i];
b[i] = last;
}
}
}
public static void main(String[] args)
{
int array1[] = new int[20];
int array2[] = new int[20];
int m, n, i;
Scanner s = new Scanner(System.in);
System.out.print("Enter the size of the array 1 :");
m = s.nextInt();
System.out.println("Enter the elements of the array 1 :");
for(i=0; i<m; i++)
array1[i] = s.nextInt();
System.out.print("Enter the size of the array 2 :");
n = s.nextInt();
System.out.println("Enter the elements of the array 2 :");
for(i=0; i<n; i++)
array2[i] = s.nextInt();
System.out.println("Array 1 :");
print_array(array1, m);
System.out.println("\nArray 2 :");
print_array(array2, n);
merge(array1, array2, m, n);
System.out.println("\n\nAfter merging two sorted arrays :");
print_array(array1, m);
print_array(array2, n);
}
static void print_array(int arr[], int n)
{
for(int i=0; i<n; i++)
System.out.print(arr[i] + " ");
}
}
Time complexity :- O( (n+m)log(n+m) )
Space complexity :- O(1)
Comments
Post a Comment