什么是归并排序？
归并排序（MergeSort）是一种基于分治法的高效排序算法，具有稳定性和较好的时间复杂度。归并排序的基本思想是将待排序数组递归地分成两个子数组，分别对这两个子数组进行排序，然后再将它们合并成一个有序数组。
归并排序的步骤
- 分解：将数组从中间分为两部分，递归地对子数组进行相同的操作，直到子数组的长度为 1（即每个子数组只有一个元素，天然有序）。
- 合并：将两个有序的子数组合并成一个有序数组。合并的过程通过比较两个子数组的元素大小，按序依次放入目标数组。
- 重复上述步骤，直到所有子数组都合并成一个有序数组。
例如，假设我们要对数组 [3, 1, 4, 1, 5, 9, 2, 6] 进行归并排序：
将数组不断分成两部分，直到每个部分只有一个元素：
[3, 1, 4, 1] 和 [5, 9, 2, 6]
再分成 [3, 1] 和 [4, 1]，以及 [5, 9] 和 [2, 6]
继续分到每个部分只有一个元素：[3], [1], [4], [1], [5], [9], [2], [6]
合并有序子数组：将 [3] 和 [1] 合并为 [1, 3]，将 [4] 和 [1] 合并为 [1, 4]
将 [5] 和 [9] 合并为 [5, 9]，将 [2] 和 [6] 合并为 [2, 6]
将 [1, 3] 和 [1, 4] 合并为 [1, 1, 3, 4]，将 [5, 9] 和 [2, 6] 合并为 [2, 5, 6, 9]
最后将 [1, 1, 3, 4] 和 [2, 5, 6, 9] 合并为 [1, 1, 2, 3, 4, 5, 6, 9]
最终得到有序数组 [1, 1, 2, 3, 4, 5, 6, 9]。
相信看完上面的例子，你已经了解了归并排序的原理，接下来我们就得用代码来实现了。
归并排序的代码实现
可以看到归并排序的思想一定可以用递归来实现，接下来，我先给大家完整的代码，之后会对代码的关键部分讲解：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void _MergeSort(int* a, int left, int right, int* tmp)
{
(left >= right)
{
;
}
mid = (left + right) / ;
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid + , right, tmp);
begin1 = left, end1 = mid;
begin2 = mid + , end2 = right;
i = left;
(begin1 <= end1 && begin2 <= end2)
{
(a[begin1] <= a[begin2])
{
tmp[i++] = a[begin1++];
}
{
tmp[i++] = a[begin2++];
}
}
(begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
(begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
(a + left, tmp + left, () * (right - left + ));
}
{
left = , right = n - ;
* tmp = (*)(n * ());
(tmp == )
{
perror();
;
}
_MergeSort(a, left, right, tmp);
}
