Combine two sorted arrays into one sorted list, without sorting.
What to build
The merge step that lies at the heart of merge sort.
Requirements
- Read the two sorted arrays.
- Print all of the numbers in increasing order, separated by single spaces.
- Use the merge method. Do not sort everything again.
Input
The first line has n, then n numbers on the next line. The third line has m, then m numbers on the last line.
Output
One line.
Constraints
n and m are from 1 to 100. Each array is already in increasing order.
Example
Input:
3
1 4 9
3
2 3 10
Output:
1 2 3 4 9 10
Why it works
The smallest remaining value is always at the front of one of the two arrays, so one comparison decides each step.
Examples
Example 1 · Input
3 1 4 9 3 2 3 10
Expected output
1 2 3 4 9 10
Example 2 · Input
1 5 3 1 2 3
Expected output
1 2 3 5
Hints
Hint 1
Keep one index for each array.
Hint 2
Compare the two current elements, and output the smaller one.
Hint 3
When one array runs out, output what is left of the other.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int n, m;
int a[100], b[100];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
for (int i = 0; i < m; i++) scanf("%d", &b[i]);
int i = 0, j = 0;
while (i < n || j < m) {
int value;
if (j >= m || (i < n && a[i] <= b[j])) {
value = a[i++];
} else {
value = b[j++];
}
printf("%d%s", value, i < n || j < m ? " " : "\n");
}
return 0;
}