共计 911 个字符，预计需要花费 3 分钟才能阅读完成。
归并算法（MERGE-SORT）（设按升序排列）
1、分冶法 — 分冶思想的介绍
将原始问题分解为几个规模较小但类似于原问题容易解决的子问题，递归地求解这些子问题，然后再合并子问题的解来建立原始问题的解。
分冶法在递归时的步骤
分解：原问题分解为子问题，子问题是原问题规模较小的实例。
解决：递归地解决子问题，若子问题足够小，则直接求解。
合并：合并子问题的解。得到原问题解。
在归并排序中的体现
分解：分解待排序的 n 个元素的序列成各自具有 n / 2 个元素的两个子序列。
解决：使用归并排序递归地排序两个子序列。
合并：合并两个已排序的子序列一产生最终已排序的序列。
2、归并排序伪代码描述
主过程：MERGE-SORT(A, startIndex, endIndex), A: 待排数组 startIndex：起始数组下标 endIndex：截止数组下标
MERGE-SORT(A, startIndex, endIndex)
if startIndex < endIndex
midIndex = (startIndex + endIndex)/2 // midIndex 取 (startIndex + endIndex)/ 2 值的底;
MERGE-SORT(A, startIndex ,midIndex)
MERGE-SORT(A, midIndex + 1,endIndex)
MERGE(A, startIndex, midIndex, endIndex)
子过程：MERGE(A, startIndex, midIndex, endIndex)
MERGE(A, startIndex, midIndex, endIndex)
n1 = midindex – startIndex + 1
n2 = endIndex – midIndex
let L[1..n1+1] and R[1..n2+1] be new arrays
for i = 1 to n1
L[i] = A[startIndex + i -1]
for j = 1 to n2
R[j] = A[midIndex + j]
L[n1+1] = Infinity
R[n2+1] = Infinity
i = 1
j = 1
for k = startIndex to endIndex
if L[i] <= R[j]
A[k] = L[i]
i = i + 1
else A[k] = R[j]
j = j + 1
