2.4K
Question: We have 2 sorted arrays and we want to combine them into a single sorted array.
Input: arr1[] = 1, 4, 6, 8, 13, 25 || arr2[] = 2, 7, 10, 11, 19, 50
Output: 1, 2, 4, 6, 7, 8, 10, 11, 13, 19, 50
One of the simplest ways to solve this problem would be to copy both the arrays into a new array and then apply some sorting technique on them. But this method will not utilize the fact that both the arrays are already sorted.
We need to apply a different approach. Here is the algorithm that we can implement.
- Initialize two variables that serve as an index to both the arrays.
- Let i point to arr1[] and j point to arr2[].
- Compare arr[i] and arr[j]
- Add the smaller element to the new array and increase the counter.
- Repeat these steps until both counters i & j have reached the end.
Here is an implementation of the above algorithm
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 67 68 | #include<stdio.h>//a function to merge two arrays//array1 is of size 'l'//array2 is of size 'm'//array3 is of size n=l+mvoid merge(int arr1[], int arr2[], int arr3[], int l, int m, int n){ //3 counters to point at indexes of 3 arrays int i,j,k; i=j=k=0; //loop until the array 1 and array 2 are within bounds while(i<l && j<m) { //find the smaller element among the two //and increase the counter if(arr1[i] < arr2[j]) { arr3[k] = arr1[i]; //increment counter of 1st array i++; } else { arr3[k] = arr2[j]; //increment counter of second array j++; } //increase the counter of the final array k++; } //now fill the remaining elements as it is since they are //already sorted while(i<l) { arr3[k] = arr1[i]; i++; k++; } while(j<m) { arr3[k] = arr2[j]; j++; k++; }}//driver program to test the above functionint main(void){ int arr1[5] = {1, 5, 9, 11, 15}; int arr2[5] = {2, 4, 13, 99, 100}; int arr3[10] = {0}; merge(arr1, arr2, arr3, 5, 5, 10); int i=0; for(i=0;i<10;i++) printf("%d ",arr3[i]); return 0;} |
