## Sunday, July 3, 2016

### Add Elements of the Second Array into the First

Add Elements of the Second Array into the First
Given two sorted arrays, A and B. Write a method merging the elements of B into A in sorted order. Assume A has a large enough buffer at the end to hold all of B's elements.

you don't need to copy the contents of A after running out of elements in B. They are already in
place.
void merge(int[] a, int[] b, int lastA, int lastB) {
int indexA = lastA - 1; /* Index of last element in array a*/
int indexB = lastB - 1; /* Index of last element in array b */
int indexMerged = lastB + lastA - 1; /* end of merged array*/

/* Merge a and b, starting from the last element in each*/
while (indexB >= 0) {
/* end of a is > than end of b */
if (indexA >= 0 && a[indexA] > b[indexB]) {
a[indexMerged] = a[indexA]; // copy element
indexA- -;
} else {
a[indexMerged] b[indexB]; // copy element
indexB--;
}
indexMerged--; // move indices
}
}

Suppose we want to merge two arrays a1 and a2. a1 has n elements and has space for n + m elements. a2 has m elements. Suppose arrays are sorted in ascendant order.
 `int``* merge(``int``* a1, ``int` `n, ``int``* a2, ``int` `m)`
 `{`
 `    ``int` `ind = m + n - 1; ``// fill resulting array from the end`
 `    ``m = m-1; n = n-1;`
 `    ``while` `(m >= 0 && n >= 0)`
 `    ``{`
 `        ``if` `(a1[n] >= a2[m])`
 `        ``{`
 `            ``a1[ind] = a1[n];`
 `            ``--n;`
 `        ``}`
 `        ``else`
 `        ``{`
 `            ``a1[ind] = a2[m];`
 `            ``--m;`
 `        ``}`
 `        ``--ind;`
 `    ``}`
 `    ``if` `(m >= 0)`
 `    ``memcpy``(a1, a2, (m + 1) * ``sizeof``(``int``));`
 `return` `a1;`
 `}`