May 042017
 

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++;
    }
}

 

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)