Merge Arrays

• We will combine two sorted lists into a single sorted list.

• Merging is a binary operation that needs more than one array.

• Other binary operations are append, concat, compare, copy.

• We don't reuse array containers, we have to merge array A and B into a new array C.

• We will take three index pointers: i at the start of array A, j at the start of array B and k at the start of array C.

struct Array *Merge(struct Array *arr1, struct Array *arr2) {
  int i, j, k;
  i = j = k = 0;
  
  struct Array *arr3 = (struct Array *)malloc(sizeof(struct Array));

  while (i < arr1->length && j < arr2->length) {
    if (arr1->A[i] < arr2->A[j])
      arr3->A[k++] = arr1->A[i++];
    else
      arr3->A[k++] = arr2->A[j++];
  }

  for (; i < arr1->length; i++)
    arr3->A[k++] = arr1->A[i];

  for (; j < arr2->length; j++)
    arr3->A[k++] = arr2->A[j];

  arr3->length = arr1->length + arr2->length;
  arr3->size = 10;

  return arr3;
}