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

如图代码为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;
}