归并和归并排序

排序算法

---

1. 归并操作：是将两个有序独立的文件合并成为一个有序文件的过程。
2. 归并排序：和快速排序的过程相反，它是两个递归调用（排序子文件）后是一个归并的过程。
   快速排序时，先分解成两个子问题后是两个递归调用（排序子文件）的过程。

1. 归并操作

1.1 基本的两路归并

将两个已经有序的数组 a 和 b 合并成一个有序的数组 c .
归并操作的过程如下：
1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针到达序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

//将有序数组a,b合并成为一个有序数组c
void mergeAB0(Item c[], Item a[], int M, Item b[], int N)
{
    int k = 0;
    int i = 0, j = 0;
    while(k < M+N)
    {
        if(i == M) //a数组已完结
        {
            c[k++] = b[j++];
            continue;
        }   
        if(j == N) //b数组已完结
        {
            c[k++] = a[i++];
            continue;
        }
        if(less(a[i], b[j]))
            c[k++] = a[i++];
        else
            c[k++] = b[j++];
    }
}

此归并是稳定的，它保持了相同关键字的相对顺序。

1.2 抽象原位归并

目标：将数组a[l],……,a[m]和a[m+1],……,a[r]合并成一个有序文件，结果保存在a[l],……,a[r].

实现：通过构建双向序列（bitonic顺序），省略了1.1中的检查是否到达数组尾部的测试操作。
将第一个数组复制到辅助数组aux[]中，将第二个数组按倒序方式紧跟第一个数组复制到aux[]中。第一个for循环移动第一个数组，使i指向l；第二个for移动第二个数组，使j指向r，为归并做好准备。接着，在归并操作（第三个for），将最大的元素当做观察哨，不管它在哪一个数组。

//抽象原位归并算法：双向序列的归并算法，不稳定
void mergeAB(Item a[], int l, int m, int r)
{
    //构建双向序列
    int i, j, k;
    for(i = m+1; i > l; i--)
        aux[i-1] = a[i-1];
    for(j = m, k = r; j < r; j++, k--)
        aux[k] = a[j+1];
    //归并操作；此时，i=l,j=r
    for(k = l; k <= r; k++)
    {
        if(less(aux[i], aux[j]))
            a[k] = aux[i++];
        else
            a[k] = aux[j--];
    }
}

此归并是不稳定的。

2. 归并排序

分治策略（1）将原文件分解成大小相等的2个子文件；（2）将2个子文件分别排序；（3）将2个有序的子文件进行合并

2.1 自顶向下的归并排序

//自顶向下的merge sort
void merge_sort(Item a[], int l, int r)
{
    if(l >= r)
        return;
    //小文件改进
    // if(r-l < 10) {insertion_sort(a, l, r); return;}
    int m = (l+r)/2;
    merge_sort(a, l, m);
    merge_sort(a, m+1, r);
    mergeAB(a, l, m, r);
}

算法分析
(1)对长度为N的文件，需进行$lgN$(树的深度)趟二路归并，每趟归并的时间为$O(N)$，故其时间复杂度无论是在最好情况下还是在最坏情况下均是$O(NlgN)$。
(2)需要一个辅助数组来暂存两有序子文件归并的结果，故其辅助空间复杂度为$O(N)$，显然它不是就地排序。
(3) 如果使用的归并算法是稳定的，排序算法就是稳定的。

2.2 自底向上的归并排序

每一个递归程序都有一个非递归程序与之对应。
原理：先求出小问题的解，在把它组合成较大问题的解。
(1) 将文件中的所有元素看作大小为1的有序子表，接着便利这些表进行1-1的归并，产生大小为2的有序子表；
(2) 然后遍历文件列表进行2-2归并，产生大小为4的有序子表
(3) 然后进行4-4归并，产生大小为8的有序子表，以此类推，直至整个表有序

通过在整个文件中进行多遍的m-m的归并，完成自底向上的归并排序，在每一遍中m加倍；仅当文件大小是m的偶数倍时，最后一个子文件的大小是m，否则最后的归并是m-x归并，x <= m

//自底向上 merge_sort
void merge_sort_BU(Item a[], int l, int r)
{
    int i, m;
    for(m = 1; m <= r-l; m *= 2) //控制每层子问题的大小
    {
        for(i = l; i <= r-m; i+= 2*m) //从最左侧，依次递增 2m
            mergeAB(a, i, i+m-1, min(i+2*m-1, r)); 
    }
}

性质 1：除了最后一个子文件外，所有子文件的大小都是2的幂，
性质 2：对N个元素的自底向上归并排序执行的遍数k，是使 $2^k >= N$成立的最小值，即 $lgN$,也是N用二进制表示的位数。

2.3 归并排序的性能特征

运行时间与 $NlgN$ 成正比，与输入无关；
使用额外的内存空间；
可以稳定实现。

3 归并排序的链表实现

4 归并排序与快速排序对比

1. 递归实现中： 快速排序，在一个递归实现中，大多数工作（划分过程）在递归递归调用前完成；而归并排序是在递归之后。
2. 非递归实现中： 快速排序必须使用栈，因为其保存了大的子问题，然后根据数据情况进行分解；归并排序的划分与数据无关。
3. 稳定性： 稳定的归并操作，就能够保证稳定的归并排序；对基于数组的快速排序实现，将数组稳定的划分是不容易的，在递归之前，稳定性已经破坏，然而基于链表的快速排序是稳定的。