分治法与归并排序

分治法（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)