归并排序是分治思想的一个很典型的应用，它将待排序数组A[0...n-1]划分为A[0...m]和A[m+1...n]两个部分（其中m=(n-1)/2）,然后对两个子数组分别排序，并以较小的时间代价将合并

一.算法

1.归并排序算法

ALGORITHM Mergesort(A[0..n-1],B[0..n-1],left,right)
//Input:待排序数组A[0...n-1],辅助数组B[0..n-1]
//Output:递增排好序的数组A

//递归终止条件，当每个子数组中只有一个元素

if(left>=right)　　　　 　　

　　return; 
m = (left+right)/2;
 
//分别对两个子数组排序
Mergesort(A,B,left,m);　 
Mergesort(A,B,m+1,right); 

//合并排好序的两个子数组
Merge(A,B,left,m,right);

2.合并排好序的子数组

 1 ALGORITHM Merge(A[0..n-1],B[0..n-1],left,mid,right)
 2 //Input:排好序的子数组A[left..mid]和A[mid+1,right]
 3 //Output:排好序的数组A[left..right]
 4 
 5 for i←left to right
 6 　　B[i] = A[i];
 7 
 8 i ← left; j ← mid+1; k ← left;
 9 
10 while i<=mid and j<=right 
11 　　if(B[i]<=B[j])　
12 　　　　A[k++] = B[i++];
13 　　else　　
14 　　　　A[k++] = B[j++];
15 
16 while(i<=mid)　　A[k++] = B[i++];
17 while(j<=right)　　A[k++] = B[j++];

二.归并排序算法的效率（假设n是2的冥）

设C(n)是对输入规模为n的数组进行归并排序的代价，C_merge(n)表示对排好序的子数组进行合并的代价，于是有下列递推关系式

 C(n) = C(n/2) + C_merge(n)

这个递归式的终止条件是C_worst(1) = 0，因为一个元素不需要再进行排序，代价为0.

在最坏情况和平均情况下，它的解都是C(n) = O(nlogn)

三.归并排序的正确性证明--循环不变式

Merge的工作是对排好序的子数组进行合并，A[left..right]划分成A[left..mid]和A[mid+1,right]两个子数组，假设A[left..mid]和A[mid+1,right]都是已经排好序的，Merge过程将它们合并成A[left..mid]这个更大的有序数组

进行Merge的详细过程如下：

　　将左右部分已分别排序的数组A[left..right]复制到辅助数组B[left..right]中，每次从两个子数组取出第一个元素进行比较，取较小的复制回原数组。算法10-17行在执行过程中，维持以下循环不变式：

　　在while循环每迭代一次时，子数组A[left..k-1]按从小到大的顺序包含数组B[left..mid]和B[mid+1,right]中的k-left个最小元素。进而，B[i]和B[j]是各自所在子数组中未被复制回数组A的最小元素。

对循环不变式的证明有三个步骤：

（1）初始化时为真

（2）每次循环开始前为真，该次循环结束时仍为真

（3）循环结束时为真

初始化：循环第一次迭代以前，有k=left,所以子数组A[left..k-1]为空，这个空的子数组包含两个已排序子数组B[left..mid]和B[mid+1,right]的k-left = 0个最小元素。又因为i和j分别为left和mid+1，所以B[i]和B[j]分别是各自所在子数组中未被复制回原数组的最小值

保持：当两个子数组中都还剩余元素时，首先假设B[i]≤B[j],那么B[i]是未复制回数组A的最小元素。因为A[left..k-1]包含k-left个最小元素。所以在B[i]复制回A以后，A[left..k]将包含k-left+1个最小元素，增加k的值和i的值后，为下次循环重新建立了新的循环不变式。若B[i]>B[j]也是同样的分析。

　　   当B[left..mid]和B[mid+1,right]中有一个子数组元素已经用完时，假设前一个已经用完，即i>mid,算法将不会执行16行的while循环。而去执行17行的while循环，此时后一个子数组中肯定还有至少一个元素，每执行一次while循环，将B[j..right]中的最小元素复制回数组A。同样保持上述循环不变式。此时i>mid，可以将A[i]看成无穷大，它同样是前一个子数组未复制回数组A的最小元素（实际情况是已经没有元素，加上它是为了便于循环不变式的分析）

终止：终止时k=right。根据循环不变式，子数组A[left...k-1]就是A[left...right]且按从小到大顺序包含B[left..mid]和B[mid+1,right]中的k-left = right-left+1个最小元素。

通过以上三个步骤，证明了循环不变式在该算法中是成立的，也就证明了归并排序算法的有效性。

四.从归并排序算法理解分治思想

　　归并排序算法是分治算法的典型应用。可以把归并排序当成分治算法的算法框架，在此基础上来解决更多的分治问题，例如对数组中逆序对的统计等

归并排序