[Algorithm_Learn_02]分治法之归并排序

1 分而治之

分而治之，各个领域都会用到的概念，基本思想即把一个复杂的问题拆分为若干个简单的子问题进行处理。作为算法领域中一个重要的算法范式，分治法又是如何应用的呢？

《算法导论》开篇就讨论了插入排序和归并排序，而归并排序就是分治法应用的一个实例。

2 归并排序

对n个数进行排序，当n足够大时，归并排序（算法时间复杂度为ϑ(nlgn)）相对于插入排序（算法时间复杂度为ϑ(n^2)）有明显的优势。

我们从一个简单的例子入手，看下归并排序是如何工作的。

现有8位美女，需要按身高从高到矮进行排序。从人的思维来讲，无论采用什么方法，最终我们每次都只能进行两两比较（计数排序法除外），因此这个问题的最小子问题就是比较两位美女的身高。将其分为四组，进行比较，每组从高到低排序，如下图。

上面一个步骤很简单，但是当我们得到4组排序后的数据后，下一步怎么做呢？我们拿其中的两组来作说明。

方法也很简单，即从每组先派出最高的一位美女进行PK，获胜者晋级，失败者继续与下一位PK，直到所有人完成PK和排序。

如此类推，将得到如下排序结果。不难看出，在这个过程中每位佳丽都与另外八位进行过一次比较（有且仅有一次）。

虽然上述过程很简单，但仍有几个问题需要思考：

1）如果输入n不是2的指数倍，如何分组？

2）归并排序的时间复杂度为什么是ϑ(nlgn)？

3 问题讨论

1）如果输入n不是2的指数倍，如何分组？

实际上归并排序分为“分解”和“合并”两步。在上面的讨论中，忽略了分解步骤，并且采用了一个输入为8的简单例子，很容易将其分为4组。

这里还要继续讨论下归并排序中的分解方法，否则是用代码无法实现算法的。分解过程实际是一个递归过程，即以迭代的方式执行⌊n/2⌋（⌊...⌋为向下取整，如果n=3，则结果为1）进行分组。还是给一个简单的例子，如下图

不难看出，合并是分解的逆序过程。

*额外的问题：为什么这里是取n/2的下界，而不是上界？

从程序设计的角度来看，n/2取下界可以通过将n右移一位得到，很巧妙吧^_^（⌊3/2⌋ = 1, 3>>1 = 1）

2）归并排序的时间复杂度为什么是ϑ(nlgn)？

合并算法的时间复杂度可以用公式

T(n)=2T(n/2)+cn

表示，设n是2的指数倍，那么上式可以展开成一个完全二叉树，有n个叶子节点，设该二叉树深度d，则2^d=cn/c，可得d=lgn.

由于二叉树中每一层子问题的时间复杂度之和为cn，故整个归并排序总的时间复杂度为：

T(n)=cn*lgn+cn=cn(lgn+1)=ϑ(nlgn)