题解 | #归并排序#

#include<iostream>
#include<string>
#include<sstream>
#include<stdlib.h>
using namespace std;
int a[100005],n=0,i;
void mergeSort(int,int);
int main(){
    string in,x;
    //freopen("input.txt","r",stdin);
    getline(cin,in);
    stringstream ss(in);
    while(ss>>x){
        int dig=0,i,flag=0;
        for(i=0;i<x.length();i++)
            if('0'<=x[i]&&x[i]<='9') dig=dig*10+(x[i]-'0');
            else if(x[i]=='-') flag=1;
        a[n++]=(flag?-dig:dig);    
    }
    mergeSort(0,n-1);
    for(printf("["),i=0;i<n;i++) printf("%d%s",a[i],i==n-1?"]":", ");
}
void mergeSort(int l,int r){
    if(l>=r) return;
    int mid=l+(r-l)/2;
    mergeSort(l,mid),mergeSort(mid+1,r);
    int *tmp=(int *)malloc(sizeof(int)*(r-l+1)),c=0,i,j;
    for(i=l,j=mid+1;i<=mid||j<=r;)
        if(i>mid||j<=r&&a[i]>a[j]) tmp[c++]=a[j++];
        else tmp[c++]=a[i++];
    for(i=0,j=l;i<c;i++) a[j++]=tmp[i];
}