Merge Sort - 归并排序
问题
用Merge Sort对长度为的无序序列从小到大（升序）排序。
解法
将长度为的序列分为左右两个部分，和，其中。想象和都是已排序的。如图：
将和两个已排序的序列合并即可得到更大的有序序列：
function Merge(s, k, begin, end):
let sc[begin...end] = s[begin...end]
let i = begin, j = k+1, k = begin
while i <= k and j <= end
if s[i] < s[j]
sc[k++] = s[i++]
else
sc[k++] = s[j++]
while i <= k
sc[k++] = s[i++]
while j <= end
sc[k++] = s[j++]
let s[begin...end] = sc[begin...end]
(1) Merge函数第1行：；
(2) Merge函数第2行：构造长度与相同的数组，存储和合并后的结果，该结果最终会复制给。该操作需要的空间规模为；
(3) Merge函数第3-12行：将和按序合并，得到有序序列；
(4) Merge函数第13行：将复制到上；
上述操作如图：
如何得到已排序的和？递归的对也应用上述操作即可。直到序列本身的长度小于等于1时，可以直接看作已排序序列，不需要继续递归：
function MergeSort(s, begin, end):
if end <= begin+1
return
let mid = (begin + end) / 2
MergeSort(s, begin, mid)
MergeSort(s, mid+1, end)
Merge(s, mid, begin, end)
(1) MergeSort函数第1行：在序列上调用MergeSort时；
(2) MergeSort函数第2-3行：当时，待排序的序列长度小于等于1，可以看作是已排序的，直接返回；
(3) MergeSort函数第4-7行：将待排序的序列从分开，分别递归的调用自己进行排序，得到两个已排序的，再将两部分合并即可；
复杂度
设，Merge函数的输入规模为，合并个元素的时间复杂度为。
MergeSort函数的初始输入规模为，因此调用Merge函数的输入规模为，每次递归后输入规模为上一层的，可得：
假设递归层数为，可得：
即：
将代入原始递推公式，可得：
该算法的时间复杂度为。因为每次Merge函数都会申请规模为的内存，其空间复杂度为。
归并排序适用于数据量超过内存的应用场景。试想硬盘上存储着100GB的数字需要排序，而可使用的内存只有1GB，显然无法将所有数字都放在内存中排序（也可以是分布在100台机器的数据无法存储在1台服务器这样的分布式应用场景）。从硬盘中依次读取1GB数字，对其排序后写回硬盘。反复100次即可得到100个已序的数组；再将两个已序数组进行归并排序，排序后写回硬盘，得到更长的已序数组；之后同理。最终可将100GB的数字在硬盘上排序。