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
Note: Join free Sanfoundry classes at Telegram or Youtube

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

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.