采用左闭右开区间
C++中范围往往都是左闭右开的,这里提供左闭右开的写法
核心就是退出条件为: r-l<2
#include <iostream>
using namespace std;
const int N = 100010;
int a[N], temp[N];
void merge_sort(int a[], int l, int r) {
if (r - l < 2) return;
int mid = (l + r) >> 1;
merge_sort(a, l, mid), merge_sort(a, mid, r);
int i = l, j = mid, k = 0;
while (i < mid && j < r) {
if (a[i] < a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i < mid) temp[k++] = a[i++];
while (j < r) temp[k++] = a[j++];
for (int i = l; i < r; i++) a[i] = temp[i - l];
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
merge_sort(a, 0, n);
for (int i = 0; i < n; i++) cout << a[i] << ' ';
}