归并排序 代码 + 讲解

归并排序其实就是一个简简单单的递归分治，话不多说，直接上代码

#include <bits/stdc++.h>

using namespace std;

int n;
int arr[200005];
int brr[200005];

void merge_sort(int left,int right){     //参数为每次拆分的左右边界 
	if (left >= right) return;     //当左右边界重合时，设置边界 
	int c = (left + right) / 2;      //计算中间点 
	merge_sort(left,c);      //对左半部递归 
	merge_sort(c + 1,right);     //对右半部递归
	int x = left,y = c + 1,z = left;     //合并时三个数组的下标
	while (x <= c && y <= right){     //只要左右任意一边去数字，就结束循环 
		if (arr[x] < arr[y]) brr[z++] = arr[x++];     //将少的数字放在新数组中 
		else brr[z++] = arr[y++];
	}
	//将剩余数字直接平移到新数组中汇总 
	while (x <= c) brr[z++] = arr[x++];
	while (y <= right) brr[z++] = arr[y++];
	for (int i = left;i <= right;i++) arr[i] = brr[i]; 
}

int main(){
	cin >> n;
	for (int i = 0;i < n;i++) cin >> arr[i];
	merge_sort(0,n - 1);
	for (int i = 0;i < n;i++) cout << arr[i] << " ";
	return 0;
}