Given two sorted arrays of integers, we want to merge them together in to one sorted array.
Example:
Let A= { 3, 4, 6, 10, 11, 15 } and B = {1, 2, 5, 7, 12}
Output: C= { 1, 2, 3, 4, 5, 6, 7, 10, 11,12, 15 }
Solution
Steps
- We create a new empty array, C, with the size of A+B
- we iterate through A and B simultaneously with two variables i and j and check if A[i] < B[j] and save which ever is smaller in to C.
- At this point we run out of numbers in the shorter array, if any. So we need to copy the rest of the elements from the longer array to the result array C.
public static int[] MergeArrays(int [] a, int [] b) {
int[] c = new int[a.Length + b.Length];
int i = 0,j = 0, k=0;
while ( i<a.Length && j < b.Length) {
if(a[i] < b[j]) {
c[k] = a[i];
i++;k++;
}
else {
c[k] = b[j];
j++;k++;
}
}
while (i < a.Length) {
c[k] = a[i];
i++;k++;
}
while(j < b.Length) {
c[k] = b[j];
j++;k++;
}
return c;
}