Java Program to Merge Two Arrays Without Extra Space

«
»

This is the Java Program to Merge Two Arrays Without Extra Space in Order.

Problem Description

Given two sorted arrays, merge both the arrays in order without using extra space.

advertisement

Example:
ArrayOne = [ 2, 3, 7, 8, 9]
ArrayTwo = [-2, -1, 1, 4, 5]

Output
ArrayOne = [-2, -1,, 1, 2, 3] ArrayTwo = [4, 5, 7, 8, 9]

Problem Solution

Let the two sorted arrays are arrayOne and arrayTwo. Pick the last element of the arrayTwo and search for any element in an arrayOne which is greater than the element selected. If the search is successful we place the element picked in its correct position. Finally, the last element of arrayOne is placed in its correct position in arrayTwo, to maintain the sorted order.

Program/Source Code
Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Here is the source code of the Java Program to Merge Two Arrays Without Extra Space in Order. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

  1.  
  2. // Java Program to Merge Two Arrays Without Extra Space in Order
  3. import java.io.BufferedReader;
  4. import java.io.InputStreamReader;
  5. import java.util.Arrays;
  6.  
  7. public class InplaceMerge {
  8.     // Function to merge the arrays in place
  9.     static void inPlaceMerge(int[] arrayOne,int[] arrayTwo){
  10.         int i,j,temp;
  11.         for(i=arrayTwo.length - 1;i>=0;i--){
  12.             temp = arrayOne[arrayOne.length-1];
  13.             for(j=arrayOne.length-2; j>=0 && arrayTwo[i] < arrayOne[j];j--){
  14.                 arrayOne[j+1] = arrayOne[j];
  15.             }
  16.  
  17.             if(j!=arrayOne.length-2 || temp > arrayTwo[i]){
  18.                 arrayOne[j+1] = arrayTwo[i];
  19.                 arrayTwo[i] = temp;
  20.             }
  21.         }
  22.     }
  23.     // Function to read input and display the output
  24.     public static void main(String[] args) {
  25.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  26.         int size,size1;
  27.         System.out.println("Enter the size of the two arrays");
  28.         try {
  29.             size = Integer.parseInt(br.readLine());
  30.             size1 = Integer.parseInt(br.readLine());
  31.         } catch (Exception e) {
  32.             System.out.println("Invalid Input");
  33.             return;
  34.         }
  35.         int[] arrayOne = new int[size];
  36.         int[] arrayTwo = new int[size1];
  37.         System.out.println("Enter the first array elements");
  38.         int i;
  39.         for (i = 0; i < arrayOne.length; i++) {
  40.             try {
  41.                 arrayOne[i] = Integer.parseInt(br.readLine());
  42.             } catch (Exception e) {
  43.                 System.out.println("An error occurred");
  44.             }
  45.         }
  46.         System.out.println("Enter the second array elements");
  47.         for (i = 0; i < arrayTwo.length; i++) {
  48.             try {
  49.                 arrayTwo[i] = Integer.parseInt(br.readLine());
  50.             } catch (Exception e) {
  51.                 System.out.println("An error occurred");
  52.             }
  53.         }
  54.         Arrays.sort(arrayOne);
  55.         Arrays.sort(arrayTwo);
  56.         System.out.println("Initially arrays are");
  57.         System.out.println("Array One");
  58.         System.out.println(Arrays.toString(arrayOne));
  59.         System.out.println("\nArray Two");
  60.         System.out.println(Arrays.toString(arrayTwo));
  61.         inPlaceMerge(arrayOne,arrayTwo);
  62.         System.out.println("\nArrays after merging are");
  63.         System.out.println("\nArray One");
  64.         System.out.println(Arrays.toString(arrayOne));
  65.         System.out.println("\nArray Two");
  66.         System.out.println(Arrays.toString(arrayTwo));
  67.     }
  68. }
Program Explanation

1. In function inPlaceMerge(), the loop for(i=arrayTwo.length – 1;i>=0;i–) traverses the second array from right to left.
2. The variable temp stores the last element of the arrayOne.
3. The loop for(j=arrayOne.length-2; j>=0 && arrayTwo[i] < arrayOne[j];j–) moves each arrayOne element one position ahead until correct position for arrayOne[i] is not found.
4. Finally, the condition if(j!=arrayOne.length-2 || temp > arrayTwo[i]), checks if any elements were shifted.
5. If it is true, then the elements are placed into their correct position.

Take Java Programming Practice Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
advertisement

Time Complexity: O(n2) where n is the number of elements in the array.

Runtime Test Cases
 
Case 1 (Simple Test Case - equal sized arrays):
 
Enter the size of the two arrays
5
5
Enter the first array elements
2
3
7
8
9
Enter the second array elements
-2
-1
1
4
5
Initially arrays are
Array One
[2, 3, 7, 8, 9]
 
Array Two
[-2, -1, 1, 4, 5]
 
Arrays after merging are
 
Array One
[-2, -1, 1, 2, 3]
 
Array Two
[4, 5, 7, 8, 9]
 
Case 2 (Simple Test Case - Unequal Sized arrays):
 
Enter the size of the two arrays
3
4
Enter the first array elements
6
7
8
Enter the second array elements
1
2
3
4
Initially arrays are
Array One
[6, 7, 8]
 
Array Two
[1, 2, 3, 4]
 
Arrays after merging are
 
Array One
[1, 2, 3]
 
Array Two
[4, 6, 7, 8]
 
Case 3 (Simple Test Case - Unequal sized reverse sorted arrays):
 
Enter the size of the two arrays
3
2
Enter the first array elements
5
4
3
Enter the second array elements
2
1
Initially arrays are
Array One
[3, 4, 5]
 
Array Two
[1, 2]
 
Arrays after merging are
 
Array One
[1, 2, 3]
 
Array Two
[4, 5]

Sanfoundry Global Education & Learning Series – Java Programs.

advertisement

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.