归并排序模板

归并排序要点：
分治的思想

1. 确定分界点 mid = (l + r)/2;
2. 递归排序left,right
3. 归并——合二为一(归并排序的核心)

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int a[N], tmp[N];  //tmp[]结果数组 

void merge_sort(int q[], int l, int r){
	if(l >= r) return;   //递归终止条件，区间元素个数没有或只有一个 
	
	int mid = l + r >> 1;  //确定分界点 
	
	merge_sort(q, l, mid), merge_sort(q, mid + 1, r);  //递归处理左右两段 
	
	//归并 
	int k = 0, i = l, j = mid + 1;  //k:指合并了几个数 i: 指向左半边的起点，j:指向右半边的起点 
	while(i <= mid && j <= r){   	//i小于左半边边界，j小于右半边边界 
		if(q[i] <= q[j]) tmp[k++] = q[i++];
		else tmp[k++] = q[j++];
	}	
	while(i <= mid) tmp[k++] = q[i++];  //左半边没循环完 
	while(j <= r) tmp[k++] = q[j++];    //右半边没循环完 
	
	for(int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];  //结果赋值回q[]里 
}


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