归并排序 c++

时间复杂度O(N*logN) 在数据量较小时与N方相差不大，但当数据量很大时，速度快了很多。

主要运用递归和分治的思想，递归很好写，分治比较难写。

#include

using namespace std;

void merge_sort(int a[], int l, int r) {
	if (l >= r) return;
	// 中间位置
	int mid = l + (r - l) / 2;
	// 左边排序
	merge_sort(a, l, mid);
	// 右边排序
	merge_sort(a, mid + 1, r);
	merge(a, l, r, mid);
}

void merge(int a[], int l, int r, int mid) {
	int *help = new int[r - l + 1];
	int i = 0;
	int p1 = l;
	int p2 = mid + 1;
	// 排序 
	while (p1 <= mid && p2 <= r) {
		// 左边的值优先
		help[i++] = a[p1] <= a[p2] ? a[p1++] : a[p2++];
	}
	// 当上面while循环结束时，必定只会走下面两个循环中的一个
	// 将没遍历完的值依次遍历到help中
	while (p1 <= mid) {
		help[i++] = a[p1++];
	}
	while (p2 <= r) {
		help[i++] = a[p2++];
	}
	// 赋值
	for (int i = 0; i < r-l+1; i++) {
		a[i+l] = help[i];
	}
}
int main() {
	int n;
	cin >> n;
	int arr[100000+5];
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	merge_sort(arr, 0, n - 1);
	for (int i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
	return 0;
}