归并排序算法

归并排序用的思想和快速排序类似，不同之处在于，快速排序法是在数组中选择一个数作为标杆，以这个标杆来将数组分成两边然后对这两边递归处理，直到最后数组只有一个元素的时候，排序就结束了。而归并排序则是以数组的中间下标为标杆，将数组分成两部分，递归，然后等待子递归程序结束后，那么左边和右边两个子数组分别排序完成，但是左右两个数组中的元素整合在一起的时候，排序时是什么样的还不清楚，所以最后一步就是一个普通的排序。
快速排序法在这里快速排序法

#include<iostream>
using namespace std;
const int maxn = 1000000 + 5;
int num[maxn];
int tmp[maxn];
int n;
void merge_sort(int l, int r)
{
	if (l >= r)
	{
		return;
	}
	else
	{
		int mid = (l + r) >> 1;
		merge_sort(l, mid), merge_sort(mid + 1, r);
		int k = 0, i = l, j = mid + 1;
		while (i <= mid && j <= r)
		{
			if (num[i] < num[j])
			{
				tmp[k++] = num[i++];
			}
			else
			{
				tmp[k++] = num[j++];
			}
		}
		while (i <= mid)
		{
			tmp[k++] = num[i++];
		}
		while (j <= r)
		{
			tmp[k++] = num[j++];
		}
		for (int i = l, j = 0; i <= r; i++, j++)
		{
			num[i] = tmp[j];
		}
	}
}
int main(void)
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &num[i]);
	}
	merge_sort(0, n - 1);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", num[i]);
	}
	return 0;
}