前言：

归并排序的核心思路是把数组里面的数两两分成一组，组内比较完大小之后，再把组外的融合进组内进行比较。
以下两个版本的核心思路也是这样。只是分组的方法不同。

1 递归版本（MergeSort）

1.1 核心思路

递归版本利用递归的思路，来实现对数组的分组。

以上述待排序数组为例。将第一个数定义为left，最后一个数定义为right，再将（left + right）/ 2定义为mid。
以mid为中心，把数组分为[left,mid][mid + 1,right]两个数组。得到：

重复上面的步骤，再次二分。得到：

将数组分成剩下2个数时，开始比较。从第一个数组开始比较，也就是[6,1]。比较完成后，再将[2,7]与第一个数组融合，再次进行比较。得到：

重复上面的步骤，将第一个数组的内容比较完成，再将第二个数组与第一个数组融合。得到：

继续重复上面的步骤，直到数组排序完成。得到：

1.2 实现代码

// 归并排序递归实现
void _MergeSort(int* arr, int left, int right, int* tmp)
{if (left >= right)//递归终止的信号---当数组里只剩下一个数时，就应该返回递归{return;}int mid = (left + right) / 2;//定义mid_MergeSort(arr, left, mid, tmp);//数组二分之后，先从左边接着二分_MergeSort(arr, mid + 1, right, tmp);//左边二分完成后，再看数组的右边int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int index = begin1;//运用双指针的思维，来对数组进行排序while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else {tmp[index++] = arr[begin2++];}}//循环退出，说明begin1和begin2有一个大于end2//另一个没有比较完while (begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}//收尾工作，确保两个组都能比较完for (int i = left; i <= right; i++){arr[i] = tmp[i];}//把比较好的数放回原数组。本来上述程序比较好的数本来放在tmp这个临时数组
}//核心思路是把数组分成两个数一组，一组一组比较，比较完再把下一个组融合进来比较
void MergeSort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(arr, 0, n - 1, tmp);free(tmp);
}

2 非递归版本（MergeSortNonR）

2.1 核心思路

非递归版本的核心思路就是利用区间的思维，来对数组进行区间的划分。

以上述数组为例。已知数组的大小为7。那么可以将区间的划分次数定义为n / 3 + 1。也就是3次。定义一个gap = 1。每次比较完，gap都会 *= 2。直到gap > n。再定义一个i，i是确保能把数组的比较数量。得到：

i是数组比较的区间。我们第一次比较是在区间[0,2)，比较完成后，再比较区间[2,4)，再比较[4,6)。直到数组里所有成员两两比较完之后。得到：

此时进入下一个gap，也就是gap = 2。重新开始比较。得到：

此时，再次比较数组里的成员。得到：

这里比较完成，再把数组合在一起进行比较。得到：

剩下的就是对整个数组进行比较。得到最终排序好的数组：

2.2 实现代码

// 归并排序非递归实现
void MergeSortNonR(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);for (int gap = 1; gap < n; gap *= 2)//将数组的区间划分成gap组{int index = 0;for (int i = 0; i < n; i += 2 * gap)//确保比较的成员是从两两开始的{int begin1 = i, end1 = i + gap;int begin2 = i + gap, end2 = i + 2 * gap;if (end1 > n) break;if (end2 > n) end2 = n;//end1 和 end2 的定义存在越界的风险，所以在开始比较之前，确认end1 和 end2 没有越界//双指针法进行比较并记录在tmp中while (begin1 < end1 && begin2 < end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else{tmp[index++] = arr[begin2++];}}//循环结束，说明此时begin1和begin2有一个等于end//确保begin1和begin2能比较完所有的数while (begin1 < end1){tmp[index++] = arr[begin1++];}while (begin2 < end2){tmp[index++] = arr[begin2++];}//将比较好的数从tmp中移植到原数组arrfor (int j = i; j < end2; j++){arr[j] = tmp[j];}}}free(tmp);tmp = NULL;
}

3.完整代码

#include<stdio.h>
#include<stdlib.h>
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}//打印函数
void PrintArr(int* arr,int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}// 归并排序递归实现
void _MergeSort(int* arr, int left, int right, int* tmp)
{if (left >= right)//递归终止的信号---当数组里只剩下一个数时，就应该返回递归{return;}int mid = (left + right) / 2;//定义mid_MergeSort(arr, left, mid, tmp);//数组二分之后，先从左边接着二分_MergeSort(arr, mid + 1, right, tmp);//左边二分完成后，再看数组的右边int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int index = begin1;//运用双指针的思维，来对数组进行排序while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else {tmp[index++] = arr[begin2++];}}//循环退出，说明begin1和begin2有一个大于end2//另一个没有比较完while (begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}//收尾工作，确保两个组都能比较完for (int i = left; i <= right; i++){arr[i] = tmp[i];}//把比较好的数放回原数组。本来上述程序比较好的数本来放在tmp这个临时数组
}//核心思路是把数组分成两个数一组，一组一组比较，比较完再把下一个组融合进来比较
void MergeSort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(arr, 0, n - 1, tmp);free(tmp);
}// 归并排序非递归实现
void MergeSortNonR(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);for (int gap = 1; gap < n; gap *= 2)//将数组的区间划分成gap组{int index = 0;for (int i = 0; i < n; i += 2 * gap)//确保比较的成员是从两两开始的{int begin1 = i, end1 = i + gap;int begin2 = i + gap, end2 = i + 2 * gap;if (end1 > n) break;if (end2 > n) end2 = n;//end1 和 end2 的定义存在越界的风险，所以在开始比较之前，确认end1 和 end2 没有越界//双指针法进行比较并记录在tmp中while (begin1 < end1 && begin2 < end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else{tmp[index++] = arr[begin2++];}}//循环结束，说明此时begin1和begin2有一个等于end//确保begin1和begin2能比较完所有的数while (begin1 < end1){tmp[index++] = arr[begin1++];}while (begin2 < end2){tmp[index++] = arr[begin2++];}//将比较好的数从tmp中移植到原数组arrfor (int j = i; j < end2; j++){arr[j] = tmp[j];}}}free(tmp);tmp = NULL;
}int main()
{//int arr[] = { 5,2,7,8,1,3,9,4,6 };int arr[] = { 4,2,1,8,5,6,9,5 };//int arr[] = { 2,3,6,5 };int sz = sizeof(arr) / sizeof(int);printf("排序前：");PrintArr(arr, sz);//MergeSort(arr, sz);MergeSortNonR(arr, sz);printf("排序后：");PrintArr(arr, sz);return 0;
}

完