归并：把俩个或多个已经有序的序列合并成一个。
二路归并：每选出一个小元素就需对比关键字1次
多路归并：每选出一个小元素就需对比关键字(n-1)次
对于二路归并排序：形似倒立的二叉树
- 1.二叉树的第h层最多有2h-1个结点，若树高为h，则应满足n ≤ 2h-1，即h-1 = ┌log2n┐
结论：n个元素进行2路归并排序，归并趟数=┌log2n┐ - 2.每趟归并时间复杂度为O(n)，则算法时间复杂度为O(nlog2n)
- 3.空间复杂度=O(n)，来自辅助数组temp
- 4.稳定性：稳定
代码实现：
// 辅助数组
int *temp = (int *)malloc(ArrSize*sizeof(int));
// mid分开的俩组各自有序，将俩部分归并
void MergeArr(int arr[], int low, int mid, int high){
int i,j,k;
for(k=low; k<=high; k++){
temp[k] = arr[k];
}
for(i=low, j=mid+1,k=i; i<=mid && j<=high; k++){
if(temp[i] <= temp[j]){
arr[k] = temp[i++]; // 将较小值复制到arr中
}else{
arr[k] = temp[j++];
}
}
while(i <= mid){
arr[k++] = temp[i++];
}
while(j <= high){
arr[k++] = temp[j++];
}
}
// 归并排序
void MergeSort(int arr[], int low, int high){
if(low < high){
int mid = (low+high)/2; // 从中间划分
MergeSort(arr, low, mid); // 对左分区归并排序
MergeSort(arr, mid+1, high); // 对右分区归并排序
MergeArr(arr, low, mid, high)
}
}
总结
归并排序中在递归调用那块代码可能不好理解，在MergeSort中第三行和第四行代码分别是对由mid相分的俩个区间进行分别递归，最后在递归的最底层只是比较俩个数据，最后跳出递归。
