Given two sorted arrays of size m and n respectively. Also given an empty third array of size (m+n). write code to merge the two arrays and store the result in the third array.
INPUT ARRAYS: a = {1, 4, 5, 9} b = {0, 2, 3, 7, 15, 29} OUTPUT: c = {0, 1, 2, 3, 4, 5, 7, 9, 15, 29}
Merging logic use three pointers, each pointing to the first element of each array respectively.
Compare the element at position a and b, and move the smallest of the two at position c. Then increment the pointer whose value is mover to c, also increment c and repeat the same.
Initially value-at b is less than value-at a, so it is moved to c and both b and c are incremented
Keep on doing this until one of the two arrays exhaust, and then copy all the elements from the other array to output array.
Code
/** Merge 2 arrays a & b and store final values in c. */ void merge(int *a, int m, int *b, int n, int *c) { int i=0,j=0,k=0; // Merging the two arrays while(i<m && j<n){ if(a[i] < b[j]){ c[k] = a[i]; i++; }else{ c[k] = b[j]; j++; } k++; } // Elements left in first array if(i<m) while(i<m){ c[k] = a[i]; i++; k++; } // Elements left in second array else while(j<n){ c[k] = b[j]; j++; k++; } }