一、归并（Merge）

1. 概念

将两个有序数列合并成一个有序数列，我们称之为“归并”。

 

2. 算法思路及实现

设两个有序的子序列(相当于输入序列)放在同一序列中相邻的位置上：array[low..m]，array[m + 1..high]，先将它们合并到一个局部的暂存序列 temp (相当于输出序列)中，待合并完成后将 temp 复制回 array[low..high]中，从而完成排序。

在具体的合并过程中，设置 i，j 和 p 三个指针，其初值分别指向这三个记录区的起始位置。合并时依次比较 array[i] 和 array[j] 的关键字，取关键字较小（或较大）的记录复制到 temp[p] 中，然后将被复制记录的指针 i 或 j 加 1，以及指向复制位置的指针 p 加 1。重复这一过程直至两个输入的子序列有一个已全部复制完毕(不妨称其为空)，此时将另一非空的子序列中剩余记录依次复制到 array 中即可。

c语言实现如下:

void merge(int* array, int low, int mid, int high){    assert(array && low >= 0 && low <= mid && mid <= high);    int* temp = (int*)malloc((high - low + 1) * sizeof(int));    if (!temp) {        printf("Error:out of memory!");        return;    }    int i = low;    int j = mid + 1;    int index = 0;    while (i <= mid && j <= high) {        if (array[i] <= array[j]) {            temp[index++] = array[i++];        }        else {            temp[index++] = array[j++];        }    }    while (i <= mid) {        temp[index++] = array[i++];    }    while (j <= high) {        temp[index++] = array[j++];    }    memcpy((void*)(array + low), (void*)temp, (high - low + 1) * sizeof(int)) ;    free(temp);}

 

二、 归并排序（Merge Sort）概念

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

归并排序有多路归并排序、两路归并排序，可用与内排序，也可用于外排序，本文仅对内排序的两路归并方法进行讨论。

 

三、归并排序思路及实现

1. 从下往上的归并排序

• 把n个记录看成n个长度为1的数列（因为长度为1，所以自然有序）。
• 进行两两归并，得到n/2个长度为2的有序数列，再将这些数列两两合并，得到n/4个长度为4的有序数列，重复这个过程，直到合并成一个数列为止。

过程如下图所示：

C语言实现：

// 对 [0, length - 1] 做一趟归并长度为 n  的归并排序void merge_pass(int* array, int length, int n){    assert(array && length >= 1 && n >= 1);    int i;    int sortLength = 2 * n;    // 归并长度为 n 的两个相邻子序列    for(i = 0; i + sortLength - 1 < length; i = i + sortLength) {        merge(array, i, i + n - 1, i + sortLength - 1);    }    // 若 i + n - 1 < length - 1，则剩余一个子文件轮空，无须归并。    // 尚有两个子序列，其中后一个长度小于 n, 归并最后两个子序列。    if (length - 1 > i + n - 1) {        merge(array, i, i + n - 1, length - 1);    }}// 用分治法自下向上进行二路归并排序//void merge_sort(int* array, int length){    assert(array && length >= 0);    int n;    for(n = 1; n < length; n = (n << 1)) {        merge_pass(array, length, n);    }}

优点是效率高，缺点是代码可读性差。

 

2. 从上往下的归并排序

具体的实现有三个步骤：

• 分解 -- 将当前区间一分为二，即求分裂点 mid = (low + high)/2;
• 求解 -- 递归地对两个子区间a[low...mid] 和 a[mid+1...high]进行归并排序。递归的终结条件是子区间长度为1。
• 合并 -- 将已排序的两个子区间a[low...mid]和 a[mid+1...high]归并为一个有序的区间a[low...high]。

如下图所示：

C语言实现：

void merge_sort_dc_impl(int* array, int low, int high){    assert(array && low >= 0);    int mid;    if (low < high) {        mid = (low + high) >> 1;        merge_sort_dc_impl(array, low, mid);        merge_sort_dc_impl(array, mid + 1, high);        merge(array, low, mid, high);    }}// 用分治法自上向下进行排序void merge_sort_dc(int* array, int length){    assert(array && length >= 0);    merge_sort_dc_impl(array, 0, length - 1);}

 

四、时间复杂度及稳定性

1. 时间复杂度

长度为n的序列需要进行logn次二路归并才能完成排序（归并排序的形式其实就是一棵二叉树，需要遍历的次数就是二叉树的深度），而每趟归并的时间复杂度为O(n)，因此归并排序的时间复杂度为O(nlogn)。

 

2. 排序稳定性

所谓排序稳定性，是指如果在排序的序列中，存在两个相等的两个元素，排序前和排序后他们的相对位置不发生变化的话，我们就说这个排序算法是稳定的。

排序算法是稳定的算法。

 

五、参考

1.

2.

3.

（完）