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

Popular posts from this blog

4.Sort an array of 0's, 1's & 2's.

1. Reverse

3. Height of Binary tree