- 将两个或两个以上的子序列合并成一个子序列
- 一般是每次将两个子序列合并到一起，所以一般也叫二路归并排序
- 直到合并为一个子序列停止，此时便有序了
不同颜色代表不同的组
| 原始数据 | 45，56，42，5，8，23，51，89，80，7，4 |
| 第一次归并（一一归并） | 45，56，5，42，8，23，51，89，7，80，4 |
| 第二次归并（二二归并） | 5，42，45，56，8，23，51，89，4，7，80 |
| 第三次归并（四四归并） | 5，8，23，42，45，51，56，89，4，7，80 |
| 第四次归并（八八归并） | 4，5，7，8，23，42，45，51，56，80，89 |
void Merge(int* ar, int len, int gap)
{
int low1 = 0;
int high1 = low1 + gap - 1;
int low2 = high1 + 1;
int high2 = low2 + gap - 1 < len ? low2 + gap - 1 : len - 1;
int* br = (int*)malloc(sizeof(int) * len);
assert(br != nullptr);
int count = 0;
while (low2 < len) //low2
代码分析：
- 时间复杂度：MergeSort这个函数的里边的for循环执行的次数为次，每次调用的Merge函数里边相当于把整个数组遍历一遍，所以执行n次，所以时间复杂度为O()
- 空间复杂度：每次执行Merge函数都要开辟len个大小的空间，所以空间复杂度为O(n)
- 稳定性：是稳定的排序算法，可以自己遍历整个过程来体会
