前言

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

算法思想

该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

动态效果示意图：

分而治之：

1、分阶段

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为logn。

2、治阶段
再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。

代码实现

#include <stdio.h>
#define MAX 1000001

int a[MAX], b[MAX];
//将两段有序的区间合并为一段，复杂度为线性
void Merge(int a[], int low, int mid, int high) {
    int i = low, j=mid+1, k = low;
    while(i!=mid+1 && j!=high+1) {
        if(a[i] >= a[j])
            b[k++] = a[j++];
        else
            b[k++] = a[i++];
    }
    while(i != mid+1)
        b[k++] = a[i++];
    while(j != high+1)
        b[k++] = a[j++];
    for(i=low; i<=high; i++)
        a[i] = b[i];
}
//归并排序
void MergeSort(int a[], int low, int high) {
    int mid;
    if(low < high) {
        mid = (low + high) / 2;
        MergeSort(a, low, mid);//前面部分
        MergeSort(a, mid+1, high);//后面的部分
        Merge(a, low, mid, high);//合并
    }
}
int main() {
    int i, n;
    scanf("%d",&n);
    for(i=0; i<n; i++) scanf("%d",&a[i]);
    MergeSort(a, 0, n-1);
    for(i=0; i<n; i++)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}

算法分析

1、归并排序算法的性能

其...

课后习题

【2012年真题】设有 6 个有序表 A、B、C、D、E、F，分别含有 10、35、40、50、60 和 200 个数据元素，各 表中元素按升序排列。要求通过 5 次两两合并，将 6 个表最终合并成 1 个升序表，并在最坏情况下比较 的总次数达到最小。请问答下列问题。 
1）给出完整的合并过程，并求出最坏情况下比较的总次数。 
2）根据你的合并过程，描述 N（N≥2）个不等长升序表的合并策略，并说明理由。 

参考答案：
本题同时对多个知识点进行了综合考查。对有序表进行两两合并考查了归并排序中Merge()函数；对合并过程的设计考查了哈夫曼树和最佳归并树。外部排序属于大纲新增考点。 
1）对于长度分别为 m，n 的两个有序表的合并，最坏情况下是一直比较到两个表尾元素，比较次数为 m+n-1 次。故，最坏情况的比较次数依赖于表长，为了缩短总的比较次数，根据哈夫曼树（最佳归并树）思想的启发，可采用如图所示的合并顺序。 

根据上图中的哈夫曼树，6 个序列的合并过程为： 
第 1 次合并：表 A 与表 B 合并，生成含有 45 个元素的表 AB； 
第 2 次合并：表 AB 与表 C 合并，生成含有 85 个元素的表 ABC； 
第 3 次合并：表 D 与表 E 合并，生成含有 110 个元素的表 DE； 
第 4 次合并：表 ABC 与表 DE 合并，生成含有 195 个元素的表 ABCDE； 
第 5 次合并：表 ABCDE 与表 F 合并，生成含有 395 个元素的最终表。 
由上述分析可知，最坏情况下的比较次数为：第 1 次合并，最多比较次数=10+35-1=44；第 2 次合并，最多比较次数=45+40-1=84；第 3 次合并，最多比较次数=50+60-1=109；第 4 次合并，最多比较次数=85+110-1=194；第 5 次合并，最多比较次数=195+200-1=394。 
故，比较的总次数最多为：44+84+109+194+394=825 
2）各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。