Merge Without Extra Space - Given two sorted arrays arr1[] and arr2[] in non-decreasing order with size n and m. The task is to merge the two sorted arrays into one sorted array (in non-decreasing order).

MergeTwoSortedArray.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class MergeTwoSortedArray {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner userInput = new Scanner(System.in);
		
		System.out.println("Enter 1st Sorted Array");
		String [] sFirstSortedArray = userInput.nextLine().split(" ");
		ArrayList<Integer> iFirstSortedArray = new ArrayList<Integer>(sFirstSortedArray.length);
		for (int i = 0; i < sFirstSortedArray.length; i++) {
			iFirstSortedArray.add(Integer.parseInt(sFirstSortedArray[i])) ;
		}
		
		System.out.println("Enter 2nd Sorted Array");
		String [] sSecondSortedArray = userInput.nextLine().split(" ");
		ArrayList<Integer> iSecondSortedArray = new ArrayList<Integer>(sSecondSortedArray.length);
		for (int i = 0; i < sSecondSortedArray.length; i++) {
			iSecondSortedArray.add(Integer.parseInt(sSecondSortedArray[i]));
		}
		
		for (int i = 0; i < iFirstSortedArray.size(); i++) {
			if(iFirstSortedArray.get(i)>iSecondSortedArray.get(0)) {
				/*
				 * 1. Swap the current Element of 1st array with smallest element of 2nd array
				 * 2. Sort the 2nd Array 
				 */
				int temp = iSecondSortedArray.get(0);
				iSecondSortedArray.set(0, iFirstSortedArray.get(i));
				iFirstSortedArray.set(i, temp);
				Collections.sort(iSecondSortedArray);
			}
		}
		// Print 1st Array followed by 2nd Array
		System.out.printf("%s %s",iFirstSortedArray, iSecondSortedArray);
		
		userInput.close();
	}

}