基本思想：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
算法流程：（迭代+两个有序数列合并为一个有序数列）
时间复杂度：O(nlog(n))，归并算法是一种稳定排序算法。
归并排序：
void MergeSort(int a[], int first, int last, int temp[]){ if (first<last){ int mid = (first+last)/2; MergeSort(a, first, mid, temp); MergeSort(a, mid+1, last, temp); MergeArr(a, first, mid, last, temp); } }
子集排序：
void MergeArr(int a[], int first, int mid, int last, int temp[]) { int i = first, j = mid+1; int m = mid, n = last; int k=0; //通过比较，归并数列a和b while (i<=m && j<=n) { if (a[i]<a[j]) temp[k++] = a[i++]; else temp[k++] = a[j++]; } //将数列a或者b剩余的元素直接插入到新数列后边 while (i<=m) temp[k++] = a[i++]; while (j<=n) temp[k++] = a[j++]; for (i=0; i<k; i++) a[first+i] = temp[i]; }
原文：https://www.cnblogs.com/x5115x/p/12638219.html