数据结构：归并排序

归并排序（Merging Sort）就是将两个或两个以上的有序表合并成一个有序表的过程。将两个有序表合并成一个有序表的过程称为2-路归并，2-路归并是最简单、最常用的归并排序算法，也是本篇文章主要讨论的内容。

一、算法思想

2-路归并排序算法的思想是：将含有n个记录的初始序列看成是n个有序的子序列，每个子序列的长度为1。两两归并，得到 $\lceil n/2 \rceil$ 个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止。

如下图，是将一组关键字序列为 $\{49, 38, 65, 97, 76, 13, 27\}$ 的待排序记录，看成是7个长度为1的子序列后，进行2-路归并排序的过程。

在2-路归并排序中，每趟排序的核心操作是，将待排序序列中前后相邻的两个有序序列合并为一个有序序列。该操作的算法步骤为：设两个有序表存放在同一数组中相邻的位置（R[low…mid]和R[mid+1…high]）上，每次分别从两个表中取出一个记录进行关键字的比较，将较小者放入T[low…high]中，重复此过程，直至其中一个表为空，最后将另一非空表中余下的部分直接复制到T中。相应的算法描述如下：

// 将两个有序表R[low..mid]和R[mid+1..high]，合并为有序表T[low..high]
void Merge(RedType R[], RedType T[], int low, int mid, int high)
{
    // 初始化i、j、k，分别指向有序表R[i..mid]、R[j..high]、T[low..high]的起始位置
    i=low; j=mid+1; k=low;

    // 将R[low..high]中的记录，由小到大地并入T中
    while(i<=mid&&j<=high)
    {
        if(R[i].key<=R[j].key) T[k++]=R[i++];
        else T[k++]=R[j++];
    }

    // 将R[i..mid]中的剩余记录，复制到T中
    while(i<=mid) T[k++]=R[i++];
    
    // 将R[j..high]中的剩余记录，复制到T中
    while(j<=high) T[k++]=R[j++];
}

二、算法步骤

与快速排序类似，2-路归并排序也可以利用递归实现子序列的划分。首先把整个待排序序列划分为两个长度大致相等的子序列，然后对这两个子序列分别递归地进行排序，最后再把它们合并。2-路归并排序算法的步骤为：将R[low…high]中的记录归并排序后放入T[low…high]中。当序列长度等于1时，递归结束，否则：

将当前序列一分为二，求出分裂点mid；
对子序列R[low…mid]递归，进行归并排序，结果放入S[low…mid]中；
对子序列R[mid+1…high]递归，进行归并排序，结果放入S[mid+1…high]中；
调用算法Merge，将有序的两个子序列S[low…mid]和S[mid+1…high]归并为一个有序的序列T[low…high]。

如下图，是对一组关键字序列为 $\{49, 38, 65, 97, 76, 13, 27\}$ 的待排序记录，进行2-路归并排序的过程。

三、算法描述

// 将R[low..high]归并排序后，放入T[low..high]中
void MSort(RedType R[], RedType T[], int low, int high)
{
  if(low==high) T[low]=R[low];
  else
  {
    // 将当前序列一分为二，求出分裂点mid
    mid=(low+high)/2;
    // 将子序列R[low..mid]归并排序后，放入S[low..mid]中
    MSort(R,S,low,mid);
    // 将子序列R[mid+1..high]归并排序后，放入S[mid+1..high]中
    Msort(R,S,mid+1,high);
    // 将有序序列S[low..mid]和有序序列S[mid+1..high]合并到T[low..high]
    Merge(S,T,low,mid,high);
  }
}

// 对顺序表L进行归并排序
void MergeSort(Sqlist &L)
{
  Msort(L.r, L.r, 1, L.length);
}