归并排序
#include<iostream>
using namespace std;
#include<queue>
#include<cstdio>
#include<cstdlib>
const int maxn = 1e2+1;
int arr[maxn];
int temp[maxn];
void merge(int beg, int mid, int end){
int i = beg, j = mid+1;
int t = 0;
while(i <= mid && j <= end){
if(arr[i] <= arr[j]){
temp[t++] = arr[i++];
}
else{
temp[t++] = arr[j++];
}
}
while(i <= mid){
temp[t++] = arr[i++];
}
while(j <= end){
temp[t++] = arr[j++];
}
//复制
for(int i = 0; i < t; i++) arr[beg+i] = temp[i];
}
void mergeSort(int beg, int end){
if(beg < end){
int mid = (beg+end) / 2;
mergeSort(beg, mid);
mergeSort(mid+1, end);
merge(beg, mid, end);
}
}
int main(){
//freopen("in.txt", "r", stdin);
int n;
cin >> n;
for(int i = 0; i < n; i++){
scanf("%d", &arr[i]);
}
for(int i = 0; i < n; i++){
printf("%d ", arr[i]);
}
cout << endl;
mergeSort(0,n-1);
for(int i = 0; i < n; i++){
printf("%d ", arr[i]);
}
return 0;
}