This merge loses numbers. Find out why and repair it.
What to build
A working merge of two sorted lists, made by repairing the program you are given.
Requirements
- Keep the first loop as it is.
- Make sure every number from both lists is printed.
- The output must be in increasing order.
Input
The first line has n and m. The second line has n numbers in increasing order, and the third line has m numbers in increasing order.
Output
All n + m numbers in increasing order, separated by spaces.
Constraints
1 ≤ n, m ≤ 100.
Example
Input:
3 4
2 5 9
1 6 7 10
Output:
1 2 5 6 7 9 10
Why it works
When one list runs out, the other still holds numbers, all at least as large as what has been copied. Copying them in order finishes the merge, and it is the step most often forgotten.
Examples
Example 1 · Input
3 4 2 5 9 1 6 7 10
Expected output
1 2 5 6 7 9 10
Example 2 · Input
3 1 1 2 3 9
Expected output
1 2 3 9
Hints
Hint 1
Run it on `1 2 3` and `9`. Which numbers are missing from the output?
Hint 2
The first loop stops as soon as one list runs out. Something must then copy what is left of the other list.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int n, m, a[100], b[100], out[200];
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int j = 0; j < m; j++) scanf("%d", &b[j]);
int i = 0, j = 0, k = 0;
while (i < n && j < m) {
if (a[i] <= b[j]) out[k++] = a[i++];
else out[k++] = b[j++];
}
while (i < n) out[k++] = a[i++];
while (j < m) out[k++] = b[j++];
for (int x = 0; x < k; x++) printf("%d ", out[x]);
printf("\n");
return 0;
}