ソースコード
#include <cstdio>
#include <vector>
using namespace std;
void merge(int left,int mid,int right,vector<int>& a) {
vector<int> L;
vector<int> R;
int n1=mid-left;
int n2=right-mid;
int i,j,k;
L.resize(n1+1);
R.resize(n2+1);
L[n1]=100000000;
R[n2]=100000000;
for(i=0; i<n1; ++i) {
L[i]=a[left+i];
}
for(i=0; i<n2; ++i) {
R[i]=a[mid+i];
}
i=0;
j=0;
for(k=left; k<right; ++k) {
if(L[i]<R[j]) {
a[k]=L[i];
++i;
} else {
a[k]=R[j];
++j;
}
}
return;
}
void mergeSort(int left, int right, vector<int>& a) {
if (left+1<right) {
int mid=left+(right-left)/2;
mergeSort(left,mid,a);
mergeSort(mid,right,a);
merge(left,mid,right,a);
}
return;
}
int main() {
int N;
vector<int> a;
scanf("%d",&N);
a.resize(N);
for(int i=0; i<N; ++i) {
scanf("%d",&a[i]);
}
mergeSort(0,N-1,a);
for(int i=0; i<N-1; ++i) {
printf("%d ",a[i]);
}
printf("%d\n",a[N-1]);
return 0;
}