归并排序(acwing，算法基础课)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], tmp[N];//原数组和答案数组
void merge_sort( int l, int r)
{
if (r <= l) return; //超过边界就返回
int mid = l + r >> 1; // /2
merge_sort(l, mid); // 前半部分
merge_sort(mid + 1, r);//后半部分细分
int i = l, j = mid + 1, k = 0; //
while (i <= mid && j <= r) //开始选择两个数列中最小的
{
if (a[i] <= a[j])
{
tmp[k ++ ] = a[i];
i ++;
}else{
tmp[k ++ ] = a[j];
j ++;
}
}
while (i <= mid) //处理剩余部分
{
tmp[k ++ ] = a[i ++ ];
}
while (j <= r)
{
tmp[k ++ ] = a[j ++ ];
}
for (int x = l; x <= r; x ++ )
{
// cout << a [x] <<" ";
a[x] = tmp[x - l]; // 写入原数组
}
// cout << endl;
}
int main()
{
int n, k;
cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
}
merge_sort(1, n);
for (int i = 1; i <= n; i ++ )
{
cout << a[i] << " ";
}
return 0;
}