The merge sort array in java is a divide-and-conquer method of sorting an array. The two arrays are split into sub-arrays, and then these sub-arrays are merged back together in a sorted order. The key difference is that the two arrays being merged are already sorted, which means that the merge process can be done in a more efficient manner.
Table of Contents
Algorithm for Merge sorted Array
- Create a new integer array “result” with the length of the sum of the lengths of the two input arrays (a and b).
- Initialize three pointers “i”, “j”, and “k” for a, b and result array respectively, set i = 0, j = 0, and k = 0.
- Iterate through both arrays using a while loop, compare elements at the current position of each array (a[i] and b[j]).
- If the element in array a is less than the element in array b, add a[i] to the result array (result[k] = a[i]), increment i and k.
- If the element in array b is less than or equal to the element in array a, add b[j] to the result array (result[k] = b[j]), increment j and k.
- Repeat step 3-5 until all elements of both arrays are added to the result array.
- Add remaining elements of array a (if any) to the result array using another while loop, increment i and k.
- Add remaining elements of array b (if any) to the result array using another while loop, increment j and k.
- Return the result array, containing all elements of both input arrays in sorted order.
Time Complexity:
The time complexity of this algorithm is O(n) where n is the total number of elements in both arrays and the space complexity is O(n) as well, which means it is a very efficient algorithm.
import java.util.Arrays;
public class MergeSortedArray {
public static int[] merge(int[] a, int[] b) {
int[] res = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length) {
if (a[i] < b[j]) {
res[k] = a[i];
i++;
} else {
res[k] = b[j];
j++;
}
k++;
}
while (i < a.length) {
res[k] = a[i];
i++;
k++;
}
while (j < b.length) {
res[k] = b[j];
j++;
k++;
}
return res;
}
public static void main(String[] args) {
int[] a = {1, 3, 5, 7};
int[] b = {2, 4, 6, 8};
int[] result = merge(a, b);
System.out.println(Arrays.toString(result));
}
}
Output
Conclusion
The merge sorted array is a useful tool for combining two sorted arrays into a single, sorted array. It can be adapted to work with other types of data by implementing a comparator function to compare the elements.
