归并排序（递归）
归并排序（Merge Sort）是一种基于分治法的高效排序算法，核心思想是将数组分为更小的子数组进行排序，最终合成有序序列。
算法思想
- 分解：将待排序数组递归地分为两个子数组，直到每个子数组仅仅含有一个元素。
- 合并：将两个有序数组合并为一个有序数组，通过比较元素大小依次填入新的数组，再将新数组的内容拷贝回来给原数组。
实现步骤
分解：首先对数组进行递归分组，直到子数组最后只有一个元素结束递归，每次折半。
合并：通过递归将子数组分解为一个元素，在合并的过程中对每个数据进行排序，将排序好的元素放入到新数组，每次通过递归返回逐渐扩大子数组。为了避免覆盖，先将合并的数据放在新数组里面，然后再拷贝回原来的数组。
复杂度分析
每次对半折叠为 logn，分为了左右两组，即每层为 n，总的时间复杂度就是 O(n log n)。最好最坏都是 O(n log n)，所以是很稳定的一种排序。需要开创一模一样的新数组来作为中间数组，因此空间复杂度为 O(n)。
代码实现
辅助函数
按照上面的原理，需要先开辟一个同样大小的新数组作为辅助。如果在这个开辟空间的函数中进行递归，会导致多次开辟空间，因此需要一个子函数，在子函数里面进行递归：
void Merge(int* arr, int size) {
assert(arr);
// 开辟数组
int* tmp = (int*)malloc(sizeof(int) * size);
if (tmp == NULL) {
perror("malloc");
return;
}
// 将开辟好的空间地址作为参数传给子函数
Sort(arr, tmp, 0, size - 1);
free(tmp);
tmp = NULL;
}
核心递归函数
这个子函数才是主要的函数，因为里面包括了递归、拷贝等一系列过程。
- 先对数组进行折半操作
// 每次折半
int pivot = (left + right) / 2;
- 折半之后出现了左右两个数组，分别调用递归进行再次折半，直到满足递归结束条件
// 递归结束条件
if (left >= right) {
;
}
pivot = (left + right) / ;
Sort(arr, tmp, left, pivot);
Sort(arr, tmp, pivot + , right);
