算法学习笔记----归并排序
一、算法描述
归并排序算法完全遵循分治模式，将问题分解为若干子问题，如果子问题的规模足够小，则直接求解，否则递归地求解各子问题。算法步骤如下所示：
1）将待排序的n个元素的序列分解为各具n/2个序列的两个字序列
2）使用归并排序递归地将两个子序列排序
3）将两个已排序的子序列合并，生成排好序的序列。
二、算法实现
1、递归版本
为了避免在合并两个子序列时每次都要检查是否某个子序列已全部处理完，在每个子序列最后都添加了一个“哨兵”元素。源码如下所示：
3、时间复杂度O(1)版本
这个是在搜索的时候看到的一个题目，就是在合并两个已经排好序的子序列后时，不分配临时存储左右子序列的空间，而是使用类似插入排序的方法，将右子序列的元素插入到左子序列中。虽然这种方法节省了空间，但是时间复杂度由nlg(n)变为(n^2)lgn，牺牲了性能。代码实现如下：
D(n)和C(n)相加时，相当于是把一个Θ(1)函数与另一个Θ(n)函数相加，相加的和是n的一个线性函数，即Θ(n)。因此我们将T(n)的计算公式转换为下面的形式：
为了更直观地理解T(n)的递归式，以及后面分析这个运行时间的分解，继续重写T(n)递归式。假设c为求解规模为1的为所需的时间以及在分解步骤和合并步骤处理每个数组元素所需的时间，将T(n)的递归式重写为下面的形式：
相同常量一般不可能刚好既代表求解规模为1的问题的运行时间，又代表在分解步骤和合并步骤处理每个数组元素的时间，但是这两个时间肯定都是一个常量，为了后续的分析，做这样的假设不会影响最终的结果。
为方便起见，假设n刚好是2的幂，将T(n)递归式用下面的树来表示：
树中各个节点的值相加得到T(n)的值，其中cn为分解序列和合并序列所需的时间，T(n/2)为解决子序列排序问题所需的时间。将规模为n/2的子序列的问题进一步分解，得到下面的等价树：
在第二层的递归中，两个子结点中每个引起的代价都是cn/2，但是此时子问题的规模还是没有不够小，也就是不能直接求解，所以还需要进一步的分解，直到问题规模下降到1，这时每个子问题的代价就很容易计算出来，其代价为c，如下图所示：
下面具体分析下层数的计算和每层所需的代价的计算。
第一层只有一个节点，规模为n；第二层每个节点的规模为n/2，第三层每个节点的规模为n/4，以此类推直到节点的规模为1.假设k为层数，每层节点的规模为S(k)，则得到下面的计算公式：
问题的规模为1时，k的值为lgn+1，也就是上图中分解得到的树的层数。
现在需要确定分解和组合每层节点所需要的代价。总的问题规模为n，在分解问题时每层的节点的规模为n/2^(k-1)，其中k为层数，每层各节点的问题规模相加得到的总规模仍为n，因此每层的节点个数为2^(k-1)，将每个节点所需的代价乘以节点个数，即得到每层所需要的代码，如下所示：
为了计算T(n)递归式表示的总代价，只要把各层的代价加起来，递归树有lgn+1层，每层的代价为均为cn，所以总的代价为cn(lgn+1)=cnlgn+cn。忽略低阶项和常量c，得到时间复杂度为Θ(nlgn)。从上面的分析可以看出，归并排序是一种稳定的排序算法，最坏、最好情况下时间复杂度均为Θ(nlgn)，平均时间复杂度也为Θ(nlgn)。
归并排序的空间复杂度为Θ(n)。这个空间复杂度有些疑问，网上看到这样的解释“由于归并排序在归并过程中需要与原始记录序列同样数量的存储空间存放归并结果以及递归时深度为log2n的栈空间，因此空间复杂度为O(n+logn)”，但是感觉这个解释说不通。我是这样理解的，递归就是要高度抽象，在递归式中对左半部和右半部分别排序看作一个过程，真正要考虑的空间是在对左半部和右半部排序之后合并时需要的空间，因此空间复杂度为Θ(n)。这个理解很是牵强,,,,,
