归并排序(Merge Sort)是一种高效的、通用的、基于比较的分治排序算法。大多数实现都产生了稳定的排序，意味着实现保留了排序输出中想等元素的输入顺序。归并排序是一种分治算法，由bhdjmg于1945年发明。
2.基本思想将待排序元素分成大小大致相同的两个相同子集合，分别对两个子集合进行排序，最终将排好序的子集合合并成要求的排好序的集合。
输入: 一系列的无序元素(eg.数字)组成的输入数组A。
经过: 分两步。第一步、先将整个问题递归分解成一个个只包含一个元素的子问题/子数组(eg，刚开始问题是{2,1,5,6,4,10}，直接分成2,1,5,6,4,10即可)
第二步、一步步将分解出来的子数组合并成一个排好序的数列，向两两对比每个自数组(只有1个元素)，按照大小顺序合并成一个子数组(有2个元素);再
两两对比现在的子数组，按照大小顺序合并成一个新的子数组…依此类推，知道最后两个子数组进行对比，里面元素按照大小顺序合并成最终的有序序列。
输出: 输出数组B，里面包含的元素都是A中的但是已经按照要求排好了顺序。
当数组元素个数为奇数时：
当数组元素个数为偶数时：
3.工作原理 3.1.工作流程1.将未排序的列表划分成为n个子列表，每个子列表包含一个元素(一个元素的列表被认为是排序的)。
2.反复合并子列表以产生新的排序子列表，直到只剩一个子列表。
3.2.划分的方式自顶向下
自顶向下的实现是使用递归的原理。它从书的顶端开始，然后向下操作，每次操作都问同样的问题(我需要做什么来排序这个数组?)，并且回答它(分成两个子数组,进行递归调用，合并结果)，知道我们到达树的底部。
自底向上
自底向上的实现则不需要递归。它直接从树的底部开始，然后通过遍历这些片段再将它们合并起来。
其实，任何的合并排序都可以被可视化为树上的操作。树中的叶子代表数组中的各个元素。树的每个内部节点对应于将两个较小的数组合并成一个更大数组。
4.代码实现 递归版 #include<bits/stdc++.h>#define Maxn 10001using namespace std;void Merge(int arr[], int l, int mid, int r);void MergeSort(int arr[], int l, int r);void displayArray(int arr[], int n);int main(){ int arr[Maxn]; cout << "请输入数组元素的个数: " << endl; int n; cin >> n; cout << "请在" << n << "行内分别输入一个数组元素" << endl; for(int i = 0; i < n; i++) cin >> arr[i]; cout << "数组初始状态为: " << endl; displayArray(arr, n); MergeSort(arr, 0, n-1); cout << "数组经过归并排序后的状态为: " << endl; displayArray(arr, n);}void Merge(int arr[], int l, int mid, int r){ int i, j, k; int n1 = mid - l + 1; //左半边的长度 int n2 = r - mid; //右半边的长度 int *L = new int[n1+1]; //开辟临时空间 int *R = new int[n2+1]; for(i = 0; i < n1; i++) L[i] = arr[i+l]; //下标从0开始 将数组a的元素填入 for(j = 0; j < n2; j++) R[j] = arr[j+mid+1]; L[n1] = INT_MAX; R[n2] = INT_MAX; i = 0; j = 0; for(k = l; k <= r; k++) //合并 { if(L[i] <= R[j]) //注意这里是先把L[i]的值赋给了a[k]，之后再i++ //这样是为了方便操作 //下面else语句同理 arr[k] = L[i++]; else arr[k] = R[j++]; }}void MergeSort(int arr[], int l, int r) //p->left r->right{ if(l < r) { int mid = (l + r) / 2; //q为中点 MergeSort(arr, l, mid); //完成左半部的sort MergeSort(arr, mid+1, r); //完成右半部的sort Merge(arr, l, mid, r); //将两半部的sorted的数列整合成一个数组排序 }}void displayArray(int arr[], int n){ for(int i = 0; i < n-1; i++) cout << arr[i] << " "; cout << arr[n-1] << endl;} 非递归版(之后有空再补) 5.算法分析分类：排序算法
算法种类：分治算法
数据结构：数组
最优时间复杂度：O(nlog(n))
最坏时间复杂度：O(nlog(n))
平均时间复杂度：O(nlog(n))
最坏空间复杂度：共O(n)，辅助O(n)；当使用linked list，辅助空间为O(1)
稳定性：稳定
复杂性：较复杂
(如有错误，请在评论区里指正)