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.
Solution:
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;
}
Time Complexity: O(m+n)
public int[] mergeSortedArrays(int[] largerArr, int[] smallerArr){
for (int i = 0; i < smallerArr.length; i++) {
int indexToFill= -1;
int low = 0;
int high = largerArr.length -1;
while(low smallerArr[i]){
high = indexToFill;
}else{
low = indexToFill +1;
}
}
indexToFill = low;
System.arraycopy(largerArr, indexToFill, largerArr, indexToFill + 1, largerArr.length – low -1);
largerArr[indexToFill] = smallerArr[i];
}
return largerArr;
}