Merge Two Sorted Arrays
This Java program merges two sorted arrays into a single sorted array. The program assumes that the input arrays are already sorted in non-decreasing order. The output will be a new array containing all elements from the two input arrays, sorted in non-decreasing order.
Program Structure
- Main Class: The main class contains the logic to merge two sorted arrays.
- Merge Function: A static function to perform the merging of two sorted arrays.
Java Code
/**
* This program merges two sorted arrays into a single sorted array.
*/
public class MergeSortedArrays {
/**
* Merges two sorted arrays into a single sorted array.
* @param array1 The first sorted array.
* @param array2 The second sorted array.
* @return A new sorted array containing all elements from array1 and array2.
*/
public static int[] mergeSortedArrays(int[] array1, int[] array2) {
int[] mergedArray = new int[array1.length + array2.length];
int i = 0, j = 0, k = 0;
// Merge arrays while there are elements in both arrays
while (i < array1.length && j < array2.length) {
if (array1[i] <= array2[j]) {
mergedArray[k++] = array1[i++];
} else {
mergedArray[k++] = array2[j++];
}
}
// Copy remaining elements of array1, if any
while (i < array1.length) {
mergedArray[k++] = array1[i++];
}
// Copy remaining elements of array2, if any
while (j < array2.length) {
mergedArray[k++] = array2[j++];
}
return mergedArray;
}
public static void main(String[] args) {
int[] array1 = {1, 3, 5, 7};
int[] array2 = {2, 4, 6, 8};
int[] mergedArray = mergeSortedArrays(array1, array2);
System.out.print("Merged Array: ");
for (int num : mergedArray) {
System.out.print(num + " ");
}
}
}
Explanation
The program consists of the following parts:
- mergeSortedArrays Function: This function takes two sorted arrays as input and returns a new array that is the result of merging the two input arrays. It uses three pointers:
- i: Tracks the current position in the first array.
- j: Tracks the current position in the second array.
- k: Tracks the current position in the merged array.
The function compares elements from both arrays and inserts the smaller element into the merged array. It continues this process until all elements from one of the arrays have been added to the merged array. It then adds any remaining elements from the other array.
- Main Method: The main method initializes two sorted arrays, calls the mergeSortedArrays function, and prints the merged array to the console.
Output
When the program is executed, it will output the merged array:
Merged Array: 1 2 3 4 5 6 7 8
