归并排序

/*归并排序
	分治思想
	以整个数组的最中心的点为分界点 
	递归排序左右两边
	归并，合二为一 
*/ 
#include
using namespace std;

const int N = 1e6 + 10;
int q[N];
int tmp[N];
int n;

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;
	
	while(i <= mid && j <= r)
		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(i = l, j = 0; i <= r; i ++, j ++)
		q[i] = tmp[j];
}

int main()
{
	scanf("%d", &n);
	for(int i = 0; i < n; i ++)
		scanf("%d", &q[i]);
	merge_sort(q, 0, n - 1);
	
	for(int i = 0; i < n; i ++){
		printf("%d ", q[i]);
	}
}