题目 给定你一个长度为 $n$ 的整数数列。 请你使用归并排序对这个数列按照从小到大进行排序。 并将排好序的数列按顺序输出。 输入格式输入共两行，第一行包含整数 $n$ 。 第二行包
题目
给定你一个长度为 $n$ 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式 输入共两行，第一行包含整数 $n$ 。
第二行包含 $n$ 个整数（所有整数均在 $1∼109$ 范围内），表示整个数列。
输出格式 输出共一行，包含 $n$ 个整数，表示排好序的数列。
数据范围 $1≤n≤100000$ 输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5
思路
归并排序核心思想：分治 基本流程：
- 将区间分成左右两部分，分别进行归并排序，使其有序
- 将有序的两个区间合并成一个并暂时存放至tmp数组
- 将tmp数组各值同步至数组f[l..r]
代码
#include <iostream>
using namespace std;
const int N = 100010;
int n, f[N], tmp[N];
void merge_sort(int l, int r)
{
if (l >= r) return; // 终止条件
int mid = l + r >> 1;
merge_sort(l, mid);
merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r)
{
if (f[i] <= f[j]) tmp[k ++ ] = f[i ++ ];
else tmp[k ++ ] = f[j ++ ];
}
while (i <= mid) tmp[k ++ ] = f[i ++ ];
while (j <= r) tmp[k ++ ] = f[j ++ ];
for (int i = l, j = 0; i <= r; i ++, j ++ ) f[i] = tmp[j];
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) scanf("%d", &f[i]);
merge_sort(0, n - 1);
for (int i = 0; i < n; i ++ ) printf("%d ", f[i]);
return 0;
}