Merge two sorted arrays into one sorted array. Given two sorted arrays, write a code to merge them in a sorted manner.
Input:
arr1 = { 1, 5, 6, 7}, arr2 = { 2, 5, 8, 9, 11}
Output:
{1, 2, 5, 5, 6, 7, 8, 9, 11}
Merge Two Sorted Arrays into One Sorted Array – Java Code
How to merge two sorted arrays? Let’s first discuss their algorithm and then we will write a java code to implement this algorithm.
i) Declare a new array whose size is equal to the sum of the size of array1 plus array2.
ii) Traverse both array simultaneously.
iii) Check if current element of the first array.
- If it is smaller than the current element of the second array, then store the current element of the first array into the third array and increment the index.
- If it is larger than the current element of the second array,
then store the current element of the second array in the third array and increment the index of the second array.
iv) If there are elements left in the first array, append them into the third array.
v) Similarly, If there are elements left in the second array, append them into the third array.
The time complexity of this approach is O(m+n) where m and n is the length of first and second array.
The space complexity is also O(m+n).
Find intersection of two arrays
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
/* Merge two sorted arrays into a third sorted array */ public class MergeTwoSortedArray { public static int[] merge(int[] arr1, int[] arr2) { int len1 = arr1.length; int len2 = arr2.length; //Declare a new array of size len1+len2 int[] result = new int[len1+len2]; int i = 0; int j = 0; int k = 0; /* Traverse both the arrays. */ while(i < len1 && j < len2) { /* Compare and merge them into a sorted order. */ if(arr1[i] < arr2[j]) { result[k++] = arr1[i++]; } else { result[k++] = arr2[j++]; } } /* If there are elements left in the first array, append them into the third array. */ while(i < len1) { result[k++] = arr1[i++]; } while(j < len2) { result[k++] = arr2[j++]; } return result; } public static void main(String[] args) { //Declare two arrays int[] arr1 = { 1, 5, 6, 7, 12}; int[] arr2 = { 2, 5, 8, 9, 11}; //Function call to merge both the arrays int[] result = merge(arr1, arr2); for(int i = 0; i < result.length; i++) { System.out.print(result[i] + " "); } } } |
Find the intersection of two linked lists
In this video tutorial, I have explained how we can merge two sorted arrays into a third sorted array.
