int main(void)
{
int source[] = { 7, 5, 2, 4, 6, 1, 5, 3};
int i;
printf("Before sort: ");
for (i = 0; i < ARRAY_SIZE(source); ++i) {
printf("%d ", source[i]);
}
printf("\n");
merge_sort_iterate(source, ARRAY_SIZE(source));
printf("After sort: ");
for (i = 0; i < ARRAY_SIZE(source); ++i) {
printf("%d ", source[i]);
}
printf("\n");
return 0;
}
其处理过程如下图所示（阴影部分为代码注释中提到的当前正在处理的段）：
3、时间复杂度O(1)版本
这个是在搜索的时候看到的一个题目，就是在合并两个已经排好序的子序列后时，不分配临时存储左右子序列的空间，而是使用类似插入排序的方法，将右子序列的元素插入到左子序列中。虽然这种方法节省了空间，但是时间复杂度由nlg(n)变为(n^2)lgn，牺牲了性能。代码实现如下：
[cpp]
#include
#include
#ifndef INT_MAX
#define INT_MAX ((int)(~0U>>1))
#endif
#define ARRAY_SIZE(__s) (sizeof(__s) / sizeof(__s[0]))
static void merge(int *a, int start, int mid, int end)
{
int i, left, right;
int key;
for (right = mid + 1; right <= end; ++right) {
left = right - 1;
key = a[right];
while (a[left] > key) {
a[left + 1] = a[left];
--left;
}
a[left + 1] = key;
}
}
static void merge_sort(int *a, int start, int end)
{
int mid;
if ((start >= 0) && (start < end)) {
mid = (start + end) /2 ;
merge_sort(a, start, mid);
merge_sort(a, mid + 1, end);
merge(a, start, mid, end);
}
}
int main(void)
{
int source[] = { 7, 5, 2, 4, 6, 1, 5, 3};
int i;
printf("Before sort: ");
for (i = 0; i < ARRAY_SIZE(source); ++i) {
printf("%d ", source[i]);
}
printf("\n");
merge_sort(source, 0, ARRAY_SIZE(source) - 1);
printf("After sort: ");
for (i = 0; i < ARRAY_SIZE(source); ++i) {
printf("%d ", source[i]);
}
printf("\n");
}
三、算法分析
当输入的序列只有一个元素时，归并排序需要常量时间。假设当有n个元素时，使用归并排序算法来排序需要的时间为T(n)。当有n>1个元素时，按如下方式来分解时间：
1）分解，分解步骤仅仅是计算子数组的中间位置，需要常量时间，记作D(n)，D(n)=Θ(1)。
2）解决，递归地求解两个规模均为n/2的子序列的排序问题，运行时间为2T(n/2)。
3）合并，将两个规模为n/2的子序列合并到规模为n的序列中需要的的时间记作C(n)， C(n)=Θ(n)。
根据上面的的分析，可以得到归并排序的运行时间公式，如下所示：
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)