问题标题: 酷町堂：3900 归并数组

3900   归并数组

经验值：800 时间限制：1000毫秒

题目描述 Description

现在给出两个数组，a和b，这两个数组都是从小到大排列好的。现在请尝试将这两个数组合并成一个数组c，并且最后c数组也需是有序的。

输入描述 Input Description

第一行，一个整数m
第二行，为m个从小到大排列的整数
第三行，一个整数n
第四行，为n个从小到大排列的整数

输出描述 Output Description

一行，m+n个从小到大排列的整数

样例输入 Sample Input

3 1 3 5 2 2 4

样例输出 Sample Output

1 2 3 4 5

数据范围及提示 Data Size & Hint

m, n < 1000000

55分，样例过了

#include<iostream>
using namespace std;
int n,a[1000005],b[1000005],c[2000010];
void merge(int a[],int l,int r){
    int mid=(l+r)/2,i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r){
        if(a[i]<a[j]) b[k++]=a[i++];
        else b[k++]=a[j++];
    }
    while(i<=mid) b[k++]=a[i++];
    while(j<=r) b[k++]=a[j++];
    for(int i=l;i<=r;i++) a[i]=b[i];
}
void merge_sort(int a[],int l,int r){
    if(l==r) return;
    int mid=(l+r)/2;
    merge_sort(a,l,mid);
    merge_sort(a,mid+1,r);
    merge(a,l,r);
}
int main(){
    int m,n;
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i];
    }
    cin>>n;
    for(int i=m+1;i<=m+n;i++){
        cin>>b[i];
    }
    for(int i=1;i<=m;i++){
        c[i]=a[i];
    }
    for(int i=m+1;i<=m+n;i++){
        c[i]=b[i];
    }
    merge_sort(c,1,m+n);
    for(int i=1;i<=m+n;i++){
        cout<<c[i]<<" ";
    }
    return 0;
}