一、归并排序

1、归并排序的思想

假设我们要排一个升序的数组
先看下面的动图

假设有两组升序数据
我们设置 ptr1 和 ptr2 来代表数组下标
将两数据进行比较，将小的填入一个新的数组
当两个数组中的数都进入新的数组
接下来我们只需要将该数组复制到原数组中
就完成了排序

如果我们要排一个升序数组
就要将它分成两个小的升序数组

若想得到两个小的升序数组
就要将每一个小的升序数组分成两个更小的升序数组

。。。。。。

————————————————————————————
于是我们想到了用递归的方式
一层层递归
直到只剩下一个不用数据，然后返回进行排序

2、归并排序代码实现（递归）

void _MergeSort(int* a, int* tmp, int left, int right)
{//返回停止条件if (left == right){return;}//取中间值int mid = (left + right) / 2;//递归//[left, mid][mid + 1, right]//递归左边_MergeSort(a, tmp, left, mid);//递归右边_MergeSort(a, tmp, mid + 1, right);//进行单次归并int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;//记录起始位置int begin = left, end = right;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[begin++] = a[begin1++];}else {tmp[begin++] = a[begin2++];}}while (begin1 <= end1){tmp[begin++] = a[begin1++];}while (begin2 <= end2){tmp[begin++] = a[begin2++];}//进行拷贝memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));}//归并排序
void MergeSort(int* a, int left, int right)
{//开辟一个复制数组int* tmp = (int*)malloc(sizeof(int) * (right - left + 1));if (tmp == NULL){perror("malloc fail:");exit(1);}//进行归并排序_MergeSort(a, tmp, left, right);//数组销毁free(tmp);tmp = NULL;
}

<1> 归并排序的递归区间

递归区间1
[left, mid][mid + 1, right]
递归区间2
[left, mid - 1][mid, right]

看这两个区间有所不同
上面代码我采用的是区间1
而没有采用区间2
因为区间2会出现死循环，导致栈溢出
看下面的图：

区间1：

区间2：

同样的 mid 但是当递归至只剩下两个时，区间2就会陷入死循环

<2> 归并排序的稳定性

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

在比较 begin1 和 begin2 时我们用的是 " <= "
这样前面的数就会在前面

在图上我们发现我们在面对相同的数时，我们会先将 ptr1 中的数填入数组，那么相同数的相对位置没有发生改变，我们说归并排序是稳定的

<3> 拷贝

//进行拷贝
memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));

我们是边排序边拷贝的
如果等到最后拷贝会有出问题的风险
memcpy函数

3、归并排序代码实现（非递归）

如果是用非递归的方式
我们可以用循环
设置gap变量，gap 每次循环结束 gap *= 2
完成整个数组的归并

代码实现：

//归并排序(非递归)
void MergeSortNonR(int* a, int left, int right)
{//开辟复制数组int* tmp = (int*)malloc(sizeof(int) * (right - left + 1));if (tmp == NULL){perror("malloc fail:");exit(1);}int gap = 1;//进行单次排序while (gap < right + 1){for (int i = 0; i < right + 1; i += gap * 2){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + gap * 2 - 1;int begin = i;printf("[%d, %d][%d, %d]", begin1, end1, begin2, end2);//当begin2超过数组区间if (begin2 > right){break;}//当只有end2超过区间if (end2 > right){end2 = right;}//单次归并while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tmp[begin++] = a[begin1++];}else{tmp[begin++] = a[begin2++];}}while (begin1 <= end1){tmp[begin++] = a[begin1++];}while (begin2 <= end2){tmp[begin++] = a[begin2++];}//将数组进行复制memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}printf("\n\n");gap *= 2;}//销毁复制数组free(tmp);tmp = NULL;
}

<1> 循环区间溢出问题

当begin2超过数组区间
if (begin2 > right)
{break;
}
当只有end2超过区间
if (end2 > right)
{end2 = right;
}

在循环过程中，除了 begin1 不会超出数组区间
其他三个都有可能超出区间
我们将所有区间都打印出来

我们发现超出区间总共分为三种情况

当 begin2 和 end1 超出区间时：
说明后面的整个区间都超出了数组的范围
那就不用归并

当 end2 超出区间时：
说明后面的一部分数没有超出区间
可以将 end2 改为区间的最大值，继续进行归并

二、总结

归并排序的时间复杂度为 O(N * logN)
是比较快的排序
但是归并排序有它的缺陷
它的空间复杂度为 O(N)
排序需要开辟空间
当排序数量过大时有风险