归并排序

• 分治策略
  为了解决一个规模较大问题，我们将其分解两个子问题，并借助递归分别得到它们的解，然后将子问题的解合并成原问题的解。
• 归并算法

算法：mergeSort(S, n)
输入: n个元素组成的无序序列
输出：经排序，S称为有序序列
{
if(1<n) //不超过一个元素组成的序列S必然有序，故可直接返回S；否则
S1=S[0..[n/2]-1]; S2 = S[[n-2]..n-1]; //将S尽可能均匀地划分为前后两个子序列
S = mergeSort(S1, [n/2])； 、、将两个有序子序列归并得到有序序列S
return S；
}