14. Merge two sorted arrays without extra space

14. Merge two sorted arrays without extra space

Problem link :- click here

package program;

public class Searching__14
{
	/*
	 	Given two sorted arrays arr1[] of size n1 and arr2[] of size n2. Each array is 
	 	sorted in non decreasing order. Merge the two arrays into one sorted array 
	 	in non decreasing order without using any extra space.
	 			arr1[] = {1, 3, 5, 7}  	arr2[] = {0, 2, 6, 8, 9}
	 			output : 0 1 2 3 4 5 6 7 8 9
	 	
	 	REPEATED QUESTION
	 	
	 	step 1 :- we will take the last element from both the arrays since one of them 
	 			should be the maximum element. we will check if the if last element
	 			of first array is maximum (if the condition is true then only the following
	 			steps are executed
	 	step 2 :- if the condition is true then we will find the correct position for the last 
	 			element of the second array and place in that position and place the 
	 			last element of the first array to the ith position in the second array
	 */
	
	static void mergeWithoutSpace(int a[], int b[], int n1, int n2)
	{
		for(int i=n2-1; i>=0; i--)
		{
			int last = a[n1-1];
			a[n1-1] = a[n1-2];
			if(last > b[i])
			{
				//we will check the correct position for b[n2-1]
				int j = 0;
				for(j=n1-2; j>=0; j--)
				{
					if(a[j] > b[i])
					{
						try{
							a[j] = a[j-1];
						}catch(ArrayIndexOutOfBoundsException e) {
						}
					}
					else
						break;
				}
				a[j+1] = b[i];
				b[i] = last;
			}
		}
	}
	
	public static void main(String[] args)
	{
		int a[] = {5, 9, 10, 15, 20};
		int b[] = {1, 2, 3, 8, 13};
		
		System.out.println("Arrays before sorting :");
		printArray(a);
		System.out.println();
		printArray(b);
		
		mergeWithoutSpace(a, b, a.length, b.length);
		System.out.println("\n\nArrays after sorting :");
		printArray(a);
		System.out.println();
		printArray(b);
	}

	static void printArray(int arr[])
	{
		for(int i=0; i<arr.length; i++)
			System.out.print(arr[i] + " ");
	}
}

Time complexity :- O( (n1+n2) log(n1+n2) )
Space complexity :- O(1)