代码

#include <cstdio>
#include <algorithm>

const int N = 1 << 23;
int a[N]; int n;

void inplace_merge_sort(int *a, int n) {
	if(n == 1) return;
	int r = n >> 1;
	inplace_merge_sort(a + r, n - r);
	while (r != 1) {
		int l = r >> 1;
		inplace_merge_sort(a, l);
		int i = 0, j = r, k = r - l;
		while (i != l && j != n) {
			if (a[i] <= a[j]) std::swap(a[i++], a[k++]);
			else              std::swap(a[j++], a[k++]);
		}
		while (i != l) std::swap(a[i++], a[k++]);
		while (j != n) std::swap(a[j++], a[k++]);
		r = r - l;
	}
	for (int i = 0; i + 1 != n && a[i] > a[i + 1]; ++i) std::swap(a[i], a[i + 1]);
	return;
}

int main(void) {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) scanf("%d", a + i);
	inplace_merge_sort(a, n);
	for (int i = 0; i < n; ++i) printf("%d ", a[i]);
	
	return 0;
}

评测结果