排序----归并排序（非递归版）

如图代码为11归并的示例，用for循环来解决。

每一次往前递归的前一小部分内部已经是有序的了。

但是我们测试的时候会发现这样一个问题，begin和end的值会存在越界的问题，而且只有begin1不会越界，因为begin1是受for循环中i的控制的。

所以当我们遇到begin越界了就不用管了，遇到end越界就修正一下

注意：每归并一组都要拷贝回去，因为：

这种情况下，只有前两组归并了，但是后两组没有归并，如果是全都归并完了再整体拷贝，那么原数组中的8 9会被覆盖，就产生丢失数据的问题了。

完整代码如下：

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	
	// gap每组归并数据的数据个数
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			// [begin1, end1][begin2, end2]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);

			// 第二组都越界不存在，这一组就不需要归并
			if (begin2 >= n)
				break;

			// 第二的组begin2没越界，end2越界了，需要修正一下，继续归并
			if (end2 >= n)
				end2 = n - 1;

			int j = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}

			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}

			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}

		printf("\n");

		gap *= 2;
	}

	free(tmp);
	tmp = NULL;
}