分治法（Divide and Conquer） 思想：将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。 分治法每层递归都包含：分解、解决、合并这三个步骤。
归并排序的关键在于“合并”步骤中两个已排序序列。通过一个辅助过程MERGE(A,p,q,r)来完成合并。假设桌上有两堆扑克牌，最顶上一张牌牌面朝上。取两堆中最上面牌较小的那一张，移开，并牌面朝下放入堆中。重复该步骤，直到一个堆变空为止。 MERGE算法的伪代码如下：
MERGE(A,p,q,r)
n1 = q-p+1
n2 = r-q+1
L[1...n1+1] & R[1,n2+1]
for i=1 to n1:
L[i] = A[p+i-1]
for j = 1 to n2
R[j] = A[q+j]
L[n1+1] = INFINITY
R[n2+1] = INFINITY
i = 1
j = 1
for k=p to r
if L[i] < R[j]
A[k] = L[i]
i++
else
A[k] = R[j]
j++
MERGE-SORT排序子数组A[p…r]中的元素：
MERGE-SORT(A,p,r)
if p<r
q = (p+r)/2
MERGE-SORT(A,p,q)
MERGE-SORT(A,q+1,r)
MERGE(A,p,q,r)
