【数据结构】八大排序——归并排序，基数排序_9个整数:96 76 14 96 80 67 38 37 99,对其进行归并排序

归并排序：

归并排序是开始将待排序列的每一个数看成一组，进行一 一合并，然后进行二二，四四等合并。

呈2的倍数递增，到2的倍数大于待排序列时停止。

比如 一组待排序列  5  6   7   2   15   4   14   9   3   10

第一次进行一 一合并 ，把每一个数看成一组稳定序列 ， 合并完 5 6   2 7   4 15    9 14    3 10

然后进行二二合并 ， 2 5 6 7     4 9 14 15      3 10

然后进行四四   2 4 5 6 7 9 14 15    3 10

最后是八八合并  2 3 4 5 6 7 9 10 14 15

因为在递增到16已经超过了待排数列的长度 ，所以到这停止 。

代码的思想是  让L1  在第一组第一个 ，H1 在第一组 最后一个  ， L2 在第二组第一个 H2在第二组最后一个 ， 两组合并完后 下标移动到下两组进行比较。 申请一个数组 在每次比较完后将数据先存到这个数组里 。

//根据传递进来的gap进行几几合并
static void Merge(int *arr, int len, int gap)
{
	//因为数据本身空间不够用  所以一进来申请一个和数组等长的动态内存
	int *brr = (int *)malloc(sizeof(int) * len);
	assert(brr != NULL);
 
 
	int L1 = 0;
	int H1 = L1+gap-1;
	int L2 = H1+1;
	int H2 = L2+gap-1 < len ? L2+gap-1 : len-1;
	int i = 0;//i代表brr的下标
 
	while (L2 < len)  // 确定最少有两个组 
	{
		while