This is the Java Program to Merge Two Arrays Without Extra Space in Order.
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]
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.
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));
}
}
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.
Time Complexity: O(n2) where n is the number of elements in the array.
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.
- Check Programming Books
- Check Java Books
- Practice Programming MCQs
- Practice BCA MCQs
- Apply for Java Internship