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.

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

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.

```
 
```

// Java Program to Merge Two Arrays Without Extra Space in Order

```
import java.io.BufferedReader;
```
```
import java.io.InputStreamReader;
```
```
import java.util.Arrays;
```
```
 
```
```
public class InplaceMerge {
```

    // Function to merge the arrays in place

    static void inPlaceMerge(int[] arrayOne,int[] arrayTwo){

```
        int i,j,temp;
```

        for(i=arrayTwo.length - 1;i>=0;i--){

            temp = arrayOne[arrayOne.length-1];

            for(j=arrayOne.length-2; j>=0 && arrayTwo[i] < arrayOne[j];j--){

                arrayOne[j+1] = arrayOne[j];

```
            }
```
```
 
```

            if(j!=arrayOne.length-2 || temp > arrayTwo[i]){

                arrayOne[j+1] = arrayTwo[i];

```
                arrayTwo[i] = temp;
```
```
            }
```
```
        }
```
```
    }
```

    // Function to read input and display the output

    public static void main(String[] args) {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

```
        int size,size1;
```

        System.out.println("Enter the size of the two arrays");

```
        try {
```

            size = Integer.parseInt(br.readLine());

            size1 = Integer.parseInt(br.readLine());

```
        } catch (Exception e) {
```

            System.out.println("Invalid Input");

```
            return;
```
```
        }
```
```
        int[] arrayOne = new int[size];
```

        int[] arrayTwo = new int[size1];

        System.out.println("Enter the first array elements");

```
        int i;
```

        for (i = 0; i < arrayOne.length; i++) {

```
            try {
```

                arrayOne[i] = Integer.parseInt(br.readLine());

```
            } catch (Exception e) {
```

                System.out.println("An error occurred");

```
            }
```
```
        }
```

        System.out.println("Enter the second array elements");

        for (i = 0; i < arrayTwo.length; i++) {

```
            try {
```

                arrayTwo[i] = Integer.parseInt(br.readLine());

```
            } catch (Exception e) {
```

                System.out.println("An error occurred");

```
            }
```
```
        }
```
```
        Arrays.sort(arrayOne);
```
```
        Arrays.sort(arrayTwo);
```

        System.out.println("Initially arrays are");

        System.out.println("Array One");

        System.out.println(Arrays.toString(arrayOne));

        System.out.println("\nArray Two");

        System.out.println(Arrays.toString(arrayTwo));

        inPlaceMerge(arrayOne,arrayTwo);

        System.out.println("\nArrays after merging are");

        System.out.println("\nArray One");

        System.out.println(Arrays.toString(arrayOne));

        System.out.println("\nArray Two");

        System.out.println(Arrays.toString(arrayTwo));

```
    }
```
```
}
```

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.

Note: Join free Sanfoundry classes at Telegram or Youtube

Time Complexity: O(n²) 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.

If you find any mistake above, kindly email to [email protected]

« Prev - Java Program to Find the Minimum Distance between Array Elements

» Next - Java Program to Check if Two Strings are Cyclic Permutations of Each Other

Related Posts:

Recommended Articles: