每天学一个算法之归并排序

归并算法（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