一、归并排序
归并排序（Merge Sort）在1945年由约翰·冯·诺伊曼（John von Neumann）首次提出。
执行流程：
不断地将当前序列平均分割成2个子序列，直到不能再分割（序列中只剩1个元素） 不断地将2个子序列合并成一个有序序列，直到最终只剩下1个有序序列。
1.1. 分割（divide）
数据分割比较容易理解，就是一个不断分隔递归的过程。
/**
* 对 [begin, end) 范围的数据进行归并排序
*/
private void sort(int begin, int end) {
// 元素只有0个或1个时，不排序
if (end - begin < 2) return;
// 取出中间分割点
int mid = (begin + end) >> 1;
// 对中间点的左边数据继续分割（递归）
sort(begin, mid);
// 对中间点的右边数据继续分割（递归）
sort(mid, end);
// 上面分割完成后，开始合并数据
merge(begin, mid, end);
}
/**
* 将 [begin, mid) 和 [mid, end) 范围的序列合并成一个有序序列
*/
private void merge(int begin, int mid, int end) {
// 合并代码（重点）...
}复制
1.2. 合并（merge）
假设分割成了左右两个序列，左右两边分别用一个指针指向待排序位置，比较两个指针位置的数据，把较小的数据放入到排序好的数组中，然后把对应较小位置的指针往后移动，反复进行比较，最终就会形成一个有序的数据列。
下面以部分数据为例，看一下分割后的数据是如何进行合并的：
但是实际上，归并排序有以下条件限制：
需要 merge
的2组序列存在于同一个数组中，并且是挨在一起的（同一块内存）。
为了更好地完成 merge
操作，最好将其中1组序列备份出来，比如[begin, mid)
（因为排序好的数据最终覆盖的是左边，所以把左边的数据进行备份，备份数据和右边数据进行合并操作）
// 简写：li(left-index)、le(left-end)、ri(right-index)、re(right-end)
li == 0
le == mid – begin
ri == mid
re == end复制
没有必要每次都创建一块内存来备份左边的数据，只需要创建一个原数组长度一半的数组即可（长数组可以容纳短数组的数据）。
在合并时，还需要有一个排序数组指针ai(array-index)
，指向下一次要插入的位置。
合并时考虑左边先遍历结束和右边先遍历结束的场景。
左边先结束：如果左边先结束，右边数组元素不需要动。
右边先结束：
如果右边先结束，左边的元素依次放入右边数组中。
private void merge(int begin, int mid, int end) {
int li = 0, le = mid - begin;
int ri = mid, re = end;
int ai = begin;
// 备份左边数组
for (int i = li; i < le; i++) {
// 是begin + i，而不是 i，因为是递归调用，begin是从0开始的但不一定是0
leftArray[i] = array[begin + i];
}
// 如果左边还没有结束
while (li < le) {
// ri < re 表示操作右边的数据
if (ri < re && array[ri] < leftArray[li]) {
array[ai++] = array[ri++];
} else { // 右边先结束
array[ai++] = leftArray[li++];
}
}
}复制
注意：
array[ri] <= leftArray[li]
就会失去稳定性。
1.3. 复杂度分析
由于涉及到递归调用，计算复杂度会比较复杂。
归并排序时，用到两次递归，每次递归消耗时间都是n/2
，合并操作是O(n)
，我们只需要计算出递归消耗的时间。
递归时间复杂度计算步骤：
假设递归消耗的时间用 T(n)
表示，则一次归并排序所花费的时间是：
T(n) = 2 * T(n/2) + O(n)复制
如果 n == 1
：
T(1) = O(1)复制
等式两边同时除以 n
：
T(n)/n = T(n/2)/(n/2) + O(1)复制
令 S(n) = T(n)/n
：
S(1) = O(1)
S(n) = S(n/2) + O(1)
= S(n/4) + O(2)
= S(n/8) + O(3)
= ...
= S(n/(2^k)) + O(k)
= S(1) + O(logn)
= O(logn)复制
综上可以得出：
T(n) = n * S(n) = O(nlogn)复制
由于归并排序总是平均分割子序列，所以最好、最坏、平均时间复杂度都是O(nlogn)
，属于稳定排序。
从代码中不难看出：归并排序的空间复杂度是O(n/2+logn) = O(n)
，n/2
用于临时存放左侧数组，logn
是因为递归调用。
常见的递推式与复杂度：
二、LeetCode
合并两个有序数组：https://leetcode-cn.com/problems/merge-sorted-array/
合并两个有序链表：https://leetcode-cn.com/problems/merge-two-sorted-lists/comments/
合并K个有序链表：https://leetcode-cn.com/problems/merge-k-sorted-lists/
