0%

数据结构与算法（4）气泡排序与归并排序

发表于 更新于 分类于 本文字数： 11k
如何将一个无序的向量转化为有序的向量，这就需要用到排序算法，本文针对向量介绍两种典型的排序算法：起泡算法与归并算法。

通过之前的两篇文章我们可以知道有序向量相对于无序向量有着更多的优势，比如它的去重操作以及查找操作都可以更快速地完成，然而我们遗留下一个问题，就是如何将一个无序的向量转化为有序的向量，这就需要用到排序算法，本文针对向量介绍两种典型的排序算法，即起泡算法与归并算法。

排序器：统一接口

1
2
3
4
5
6
7
8
9
10
11
template <typename T> 
void Vector<T>::sort ( Rank lo, Rank hi ) { //向量区间[lo, hi)排序
  switch ( rand() % 6 ) {
    case 1:  bubbleSort ( lo, hi ); break; //起泡排序
    case 2:  selectionSort ( lo, hi ); break; //选择排序（习题）
    case 3:  mergeSort ( lo, hi ); break; //归并排序
    case 4:  heapSort ( lo, hi ); break; //堆排序（第12章）
    case 5:  quickSort ( lo, hi ); break; //快速排序（第14章）
    default: shellSort ( lo, hi ); break; //希尔排序（第14章）
  } //随机选择算法以充分测试。实用时可视具体问题的特点灵活确定或扩充
}

起泡排序

1
2
3
4
5
6
7
template <typename T> //向量的起泡排序（基本版）
void Vector<T>::bubbleSort( Rank lo, Rank hi ) { //assert: 0 <= lo < hi <= size
  while( lo < --hi ) //反复起泡扫描
    for( Rank i = lo; i < hi; i++ ) //逐个检查相邻元素
      if( _elem[i] > _elem[i + 1] ) //若逆序，则
        swap( _elem[i], _elem[i + 1] ); //经交换使局部有序
}

在第一章曾以这个算法为例介绍过如何证明算法的正确性，这里按照刚才统一定义的形式将它整理为一个名为bubbleSort的算法接口。这个算法实际上可以认为是通过调用一个名为bubble的过程迭代地来进行，在每一迭代过程中都会考察当前介于lo和hi之间的所有相邻元素，只要有一对相邻元素是逆序的，就将它们交换，所以整个这样的一个过程也称作扫描交换。

这个算法的不变法具体来说，如果最初的这个向量是一个无序向量的话，那么每经过这样一趟对bubble的调用都会有一个新的元素就位，比如对于第一次而言就是全局最大的那个元素，这里用红色来表示就位的元素，那么当然互补地其它的部分也就是接下来要考察的问题的范围，就会相应地缩小一个单元，这也是减而治之。再接下来有序的部分会继续地拓展，而无序的部分会继续地缩减，整个呈现为一个不断此消绿色的这部分，和彼涨红色的这部分
这样一个过程，直到无序的部分只剩下一个元素。

不难看出每一趟对bubble的调用所需要的时间都线性正比于绿色无序部分的宽度，整体地呈现为一个算术级数的形式，所以它的总体量与它的末项成平方关系，即$O(n^2)$。然而我们并不满足于这样的结果，至少在很多情况下都是有可能改进的。

改进

可以看到这里的红色部分确实必然是有序的，但是绿色的部分未必都是无序的，事实上比如这个时候有可能其中会有一部分元素，甚至所有的元素都是有序的。那么如何尽早地判定出这种情况，从而提前结束这个算法呢？这里依赖的准则与算法最初的判定准则是一样的，也就是一个向量包括一个区间如果是完全有序的，当且仅当其中任何一对相邻的元素都是彼此顺序的，而实际上在刚刚进行完的前一次迭代中我们在某种意义上已经做过这种类似的检查了。

由此可以得出一个改进的策略：在每一次扫描交换的过程中不妨记录一下是否曾经真的存在逆序元素，如果存在的话它的充要条件是在此前做过一次交换，所以我们只要来记录一下在当下这趟扫描交换过程中是否曾经做过至少一次扫描交换，如果没有做过那么后续的各趟其实都可以省略掉，从而在实际的运行时间上有可能会有所减少，甚至大大减少。这是一个很好的策略，我们不妨把这个策略整理为下面的一段代码。

1
2
3
4
5
6
7
8
9
10
11
12
template<typename T> void Vector<T>::bubbleSort(Rank lo,Rank hi){
	while (!bubble(lo, hi--));
}  //逐趟做扫描交换，直至全序
template<typename T> void Vector<T>::bubble(Rank lo, Rank hi) {
	bool sorted = ture;  //整体有序标志
	while(++lo < hi){    //自左向右，逐一检查各相邻元素
		if (_elem[lo - 1] > _elem[lo]) {    //若逆序，则
			sorted = false;                 //意味着尚未整体有序，并需要
			swap(_elem[lo - 1], _elem[lo]); //交换
		}
		return sorted;  //返回有序标志
}

原算法整体运行时间确实可以度量为一个三角形的面积，那么对于新的改进的这个算法，它固然要做第一趟扫描交换也许还需进行若干次扫描交换，但是在某些情况下它有可能会发现不光此后的部分已经有序了，而且这个前缀也已经完全有序了，所以这时它就会及时地跳转到最后，聪明地绕过这些完全可以绕过的计算量。因此与刚才那样对比新的这个算法所执行的计算量可以度量为这样一个梯形，而不是原来的三角形，也就是说很多情况下都可以节省一定的甚至是相当多的时间。不过我们对这个算法的改进并不满足于此因为我们发现在一些其它或者说在更多的情况下，这个算法依然存在继续改进的空间。

再改进

考察这样一个向量，假设它可以分为长度相差悬殊的一个前缀以及后缀，而且后缀中的元素都已按顺序排列并严格地就位，当然相应地所有的乱序元素都集中分布于这样一个相对更短的前缀中。对于这样的一个实例，上节中已经做过优化的起泡排序算法会如何表现呢？

首先它需要做第一趟完整地扫描交换，并且确认在最后这个位置有一个元素就位，虽然它原本就是就位的。请注意虽然这个时候在这个后缀中，存在着大量的就位元素，但因为在前缀中刚才存在交换，bubble算法会返回false，那么算法接下来还会继续下去。尽管能够判定的就位元素数目会继续增加，但是与刚才同理，我们依然不能确认可以提前退出，接下来还需要进行若干次的扫描交换。那么对于这样的一个例子，总体而言需要的扫描交换的趟数不会超过这个前缀的长度r。

因为此前所做的各趟扫描交换，与其说是在对绿色的范围做处理，不如说实际影响的是这个前缀中的倒数第一个
倒数第二个 以及倒数第三个，即是在这个前缀中后面的那些元素。每一趟扫描交换所起的实质作用无非是在这样一个前缀中，令其中的一个一个的后缀元素依次就位，直到整个这个前缀中的元素完全就位。

因此这个算法总体消耗的时间应该是n乘以r，如果r取作根号n，相应地也就是n的1.5次方，即$O(n^{1.5})$。但如果能及时地检测出这样一种情况，也就是实质需要排序的元素集中在一个宽度仅为$\sqrt{n}$的区间中，而不是整个向量。那么即使套用最原始的起泡排序算法，所需要的时间也无非是$O((\sqrt{n})^2)=O(n)$。问题是如何才能够完成从1.5次方到一次方的优化转换呢？

重新审视上面的例子，所多余出来的时间消耗无非是在后缀中，对这些已就位元素的反复扫描交换，不难理解这些元素都是不必扫描交换的，可惜此前的算法版本未能及时地将它们分解出来，但它们实际上是可以分解出来的。

比如说如果我们通过某一种方法记录在上一趟扫描交换过程中所进行的最后一次交换，就很容易确定在上一趟扫描的区间中有一个多长的后缀实际上没有做过任何交换，也就是说它们中的元素都是已经就位了的。如果能这样只需要将原先的右侧标志hi直接地指向这个新的位置，而不是像刚才那样亦步亦趋地、逐个地收缩。

基于以上的分析不难得到下面的新的改进的方法，从结构上看跟刚才大体类似，依然是逐个地检查所有的相邻对，如果是逆序的就做交换，不同之处在于这里我们所记录的不再只是一个逻辑性变量，而是一个名为last的整型或者说是秩，它的初值是取作lo，而每当需要交换就将这个last更新为新的位置。在整个算法的过程中lo这个变量是持续递增的，所以当它在返回的时候，last确实名副其实地记录了最右侧也就是最后一对逆序对的位置。

1
2
3
4
5
6
7
8
9
10
11
12
template<typename T> void Vector<T>::bubbleSort(Rank lo,Rank hi){
	while (!bubble(lo, hi--));
}  //逐趟做扫描交换，直至全序
template<typename T> void Vector<T>::bubble(Rank lo, Rank hi) {
	Rank last = lo;  //最右侧的逆序对初始化为[lo-1, lo]
	while(++lo < hi){    //自左向右，逐一检查各相邻元素
		if (_elem[lo - 1] > _elem[lo]) {    //若逆序，则
			last = lo;                 //更新最右侧逆序对位置记录，并
			swap(_elem[lo - 1], _elem[lo]); //交换
		}
		return last;  //返回有序标志
}  //前一版本中的逻辑型标志sorted，改为秩last

这样我们就可以有效地来处理刚才那种情况，回到刚才那个实例，我们构造了一个足够短的乱序前缀再加一个非常长但是已经就绪了的后缀。新的算法首先也会做一趟扫描交换，当然为此花费的时间是$O(n)$。但是与刚才那个版本的不同，在这个时候它会检测出发生的最后一次扫描交换绝对不会超过绿色末尾的位置，将扫描交换的右侧界桩hi一次性地挪到那里，这等效于判断出了此后的这些元素包括最后那个元素都是已经就位的。

从算法的流程来说我们的下一趟扫描交换的区间，就不再是原先整个那个绿色的区间，而是相对要短很多的一个区间。接下来等效于只是对这样一段区间做扫描交换，因此需要花费的时间除了刚才的$O(n)$以外，主要是对应于这样的一个更小的三角形，如果边长是$\sqrt{n}$，累计也不过是再加上一个$O(n)$，与刚才的$O(n)$合并，总体不过是$O(n)$，更有意思的是这种情况在整个排序过程中有可能会多次出现。

我们也可以通过图形的方式，形象地将新的这个算法版本与之前的原始版本在时间效率上做一个对比。这个三角形 代表的是原始的起泡排序算法所需要的时间。新版本的算法所需要执行的扫描交换将会呈现为连续的一段。然后再间或地跳跃到下面一段以及再间或地有可能会跳跃到下面一段（深色部分）。换而言之这个算法的时间成本将取决于这样一个一个若干个梯形的面积总和，相对于此前那个梯形来说这种梯形的划分更加的精细，所以它节省下来的时间也会在通常的情况下相对更多。

当然在最坏的情况下这个算法依然是于事无补的，起泡排序依然注定需要$O(n^2)$的时间。

综合评价

  • 三种起泡排序在最好和最坏情况下的效率相同：最好$O(n)$，最坏$O(n^2)$

  • 输入含重复元素时，算法的稳定性（stability）是更为细致的要求

    重复元素在输入，输出序列中的相对次序，是否保持不变？（在某些问题中很敏感）

    ​ 输入：$6,7_a,3,2,7_b,1,5,8,7_c,4$

    ​ 输出：$1,2,3,4,5,6,7_a,7_b,7_c,8$ //stable

    ​ $1,2,3,4,5,6,7_a,7_c,7_b,8$ //unstable

  • 三种起泡排序算法都是稳定的，因为在起泡排序中，元素$7_a$和$7_b$的相对位置发生变化，只有一种可能：

    ​ 经分别与其他元素的交换，二者相互接近直至相邻

    ​ 在接下来一轮扫描交换中，二者因逆序而交换位置

    而起泡排序中交换，即if的判断条件是_elem[lo - 1] > _elem[lo])，严格大于，因此不会出现上面的情况

虽然起泡排序可以做大量的改进，但从最坏情况而言它依然是注定也需要$O(n^2)$的时间，所以我们非常希望能够得到一个即便在最坏情况下也能够效率更高的排序算法，这也就是下一节所要介绍的内容。

归并排序

采用包括Bubble sort在内的常规的基于比较式的算法（Comparison Based Algorithm），求解排序问题都存在一个下界$nlogn$。那么在$n^2$的上界到$nlogn$的下界之间是否存在一些其它的，相对于$n^2$而言更好的算法,甚至于是否有一个算法即使在最坏的情况下也只需要$nlogn$的时间就能完成排序呢？答案就蕴含在这一节的主题里
也就是归并排序（Merge Sort）。

归并排序算法是分治策略在算法设计中应用的又一个典型，这个算法最初是由冯·诺依曼编码实现的，所谓的分治策略在这里就是说将待排序的那个序列（向量或者列表）一分为二，这种分法很快捷只需要$O(1)$的时间，接下来 对于划分出的两个子序列分别去做递归地求解，也就是递归地排序。而当两个子序列已经分别有序之后，我们接下来要解决的一个问题就是将它们合并准确地讲是归并merge，从而构成一个完整的有序序列。

对于上面这样一个由8个元素组成的向量，首先是分沿左右划分为左和右两个子序列，这两个子序列递归地求解的过程中依然还是相对比较大，所以它们会继续递归地、各自地进行划分继续分为左左、左右以及右左和右右四个子序列。同样 它们还是不够平凡所以我们最后还要对这四个子序列继续地一分为二，最终八个元素各自成为一个独立的序列，这个时候从递归地角度讲就抵达了递归基，所有这些元素都已经不需要再继续划分下去了，因为它们各自有序了。

所以如果说前面半层是做无序向量的递归分解，接下来就要通过逐层的合并使之逐渐地变成一个大一点的，更大一点的，直到最后那个有序的序列。我们可以看到每一次都是将两个已经是有序的子序列合并为一个有序的子序列，然后再继续相邻的子序列逐对地合并构成再更大的序列，最后左右这两个各自有序的子序列再逐对地合并最终得到整体的序列。

那么如果果真能像这里所说的那样，我们就应该能够得到一个总体是$nlogn$的算法，可由下面的递推式证明，其中$O(n)$是分与并累计的时间。

可以得到：$T(n)=O(nlogn)$。

接下来的技术细节就是如何来兑现这一点呢？可以看到从这里的划分的过程是非常简单，递归也可以交给递归的机制去做，所以这里核心的任务是在怎么进行合并，或者准确地讲是怎么将两个已经有序的序列归并成一个更大的序列，这也是这个算法最关键的细节和技巧。

主算法

把刚才的思路实现为这样一段具体的代码，和所有的递归程序一样首先要处理递归基，接下来开始实质的分也就是除二取到中点，这样的话我们可以将整体的一个序列分成左和右两部分，分别由lo和mi，以及mi和hi来界定。对于这两个序列，分别是递归调用自己，mergeSort前一个序列，mergeSort后一个序列。接下来最重要的实质的工作是在merge，下面不妨来通过一个实例来理解merge算法的原理

1
2
3
4
5
6
7
8
template <typename T> //向量归并排序
void Vector<T>::mergeSort ( Rank lo, Rank hi ) { //0 <= lo < hi <= size
  if ( hi - lo < 2 ) return; //单元素区间自然有序，否则...
  int mi = ( lo + hi ) / 2; //以中点为界
  mergeSort ( lo, mi ); 
  mergeSort ( mi, hi ); //分别排序
  merge ( lo, mi, hi ); //归并
}

原理

  • 2-way merge：将两个有序序列合并为一个有序序列 S[lo, hi) = S[lo, mi) + S[mi, hi)

首先（a）图给出了两个各自有序的子序列，二路归并算法的要诀就是我们只需要把注意力关注在这两个序列的首元素上，这样一个虚线的方框是我们的关注焦点，其余的元素可以暂时不用顾及。那么我们取出这两个序列各自的首元素的时候，都要从中挑选出更小的那个元素，如果是两者相等的话，可以任意取一个。
比如 就这个例子而言

就这个例子而言首先取出的是这个2，我们将它择出来，相应地在摘除了首元素以后，后续的元素将逐次递补，也就是关注到新顶替上来的这个首元素上。同样在接下来的一轮比对中，我们考察这两个首元素的大小，并且同样地取出其中的更小的那个，4依然比5小所以4被取出，同样它的后继们会顶替上来对这个例子而言就是10。就这样逐步进行到图（h），直到最终一旦有一个向量已经变成空的，那么另一个向量所剩余的元素无论多少都直接串接在后边（因为剩余那部分必然是有序的）。

按照这样的原理，我们确实可以得到一个更大的单调序列，这种二路归并的算法实际上是非常通用的一个版本，但在这里针对于归并排序而言的，我们实际上用到的是其中的一种特例，在这个时候参与归并的两个序列实际上是来自于同一个更大的向量，只不过是由其中的三个界桩也就是lo、mi和hi来联合定义的。如果左侧的这个向量称作B，右侧的称作C的话，那么合并起来的整体的这个向量就是A。那下一小节介绍针对这样一种特殊情况，二路归并算法应该如何实现。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename T> //有序向量（区间）的归并
void Vector<T>::merge ( Rank lo, Rank mi, Rank hi ){//各自有序的子向量[lo, mi)和[mi, hi)
  T* A = _elem + lo; //合并后的向量A[0, hi - lo) = _elem[lo, hi)
  int lb = mi - lo; T* B = new T[lb]; //前子向量B[0, lb) = _elem[lo, mi)
  for ( Rank i = 0; i < lb; i++ ) B[i] = A[i]; //复制前子向量
  int lc = hi - mi; T* C = _elem + mi; //后子向量C[0, lc) = _elem[mi, hi)
  for (Rank i = 0, j = 0, k = 0; (j < lb) || (k < lc); ) {
	  if ((j < lb) && (lc <= k || (B[j] <= C[k]))) 
          A[i++] = B[j++];                          //B更小，C[k]已无或不小
	  if ((k < lc) && (lb <= j || (C[k] <  B[j]))) 
          A[i++] = C[k++];                          //C更小，或B[j]已无或更大
  }  //该循环实现紧凑；但就效率而言，不如拆分处理
  delete [] B; //释放临时空间B
}

解读一下上面的代码：首先需要将定义两个向量的三个界桩也就是lo、mi和hi作为参数传入，接下来要定义清楚ABC三个向量：首先A向量在这里将继续地保存在它输入的位置，准确地讲就是在_elem整个数据区中起自于最左侧的界桩lo的一段区间，可以直接令A指向这个区间的起点。

1
T* A = _elem + lo; //合并后的向量A[0, hi - lo) = _elem[lo, hi)

接下来是左侧的子向量B，我们需要为这个子向量申请一段空间，它的宽度应该是mi到lo之间的距离，当然还需要将A中对应的那些元素，也就是左半部分的那些元素，逐一地取出来并且复制到新开辟的这段空间中去，从而完成整体的这个子向量B的一个缓冲。

1
2
int lb = mi - lo; T* B = new T[lb]; //前子向量B[0, lb) = _elem[lo, mi)
for ( Rank i = 0; i < lb; i++ ) B[i] = A[i]; //复制前子向量

最后是C，C非常的简单，实际上定义的就是在_elem数据区中，起始于mi的这段数据，那么不同的在于右侧的子向量C并不需要另辟空间进行缓存，尽管在这里为了说明的方便，还是将它画在了上边作为一个单独的子向量。

1
int lc = hi - mi; T* C = _elem + mi; //后子向量C[0, lc) = _elem[mi, hi)

接下来就是最主要的这个循环，这也就是上节实例子所给的过程，具体来讲就是每一次我们都比较两个子向量当前的首元素取出其中更小的那个，比如说在for循环体中上面一句的情况下B更小，而在下面一句的情况下C更小，无论谁更小都把它转入到A中去。B和C首元素是由j和k这两个秩来标定的，在最初始的情况下它们都是0，分别指向B和C的第一个元素，在随后 每当有一个元素转移到A中，它们各自都会自加，从而指向下一个替补的新的首元素。而A每次纳入新元素由i指示，其初值也是0。

1
2
3
4
5
6
for (Rank i = 0, j = 0, k = 0; (j < lb) || (k < lc); ) {
	  if ((j < lb) && (lc <= k || (B[j] <= C[k]))) 
          A[i++] = B[j++];                          //B更小，C[k]已无或不小
	  if ((k < lc) && (lb <= j || (C[k] <  B[j]))) 
          A[i++] = C[k++];                          //C更小，或B[j]已无或更大
  }

当B更小的情况：严格来讲是由一系列的逻辑判断构成的，首先是一个and，我们要确定j < lb，即B中的首元素的秩应该至少没有越过它的右侧的边界，它还是合法的，也就是B[j]指向的还是一个实在的而不是虚拟的元素，接下来地有两种情况，要么C中的k已经越界，要么就是k没有越界，但是B[j]更小B[j] <= C[k]，这里我们运用了C++语言里头的“短路求值”的语法特性，否则在不满足的情况下还去进行比较求值，实际上这个k因为已经越界就会造成程序运行过程中的错误。当C更小的情况也是同理。

当然整个这个循环的退出条件也值得揣摩的，这里的条件(j < lb) || (k < lc)可以理解为是这两个位置j和k同时越界之后算法才会退出，而在这个时候无论是B还是C中的元素都已经完整地归入到了A中，成为了一个整体的序列。

正确性

为了更好地理解算法的过程，我们不妨分几种情况来给出具体的图示作进一步解释。

首先来考虑第一种情况（a)，i还是介于lo和mi之间没有越过mi这个界线，还没有进入到C这个子向量的范围，这种情况显然i不可能居于j的左侧，顶多是平齐，所以每次迭代中如果需要发生数据转移的话，无论是B[j]转移到A[i]，还是C[k]转移到A[i]，整个数据从内容来讲都不会发生覆盖，是安全的，功能上讲也是正确的。

再来看相对复杂一点的情况(b)，也就是当i在持续增加之后，终会越过mi，进入C的区域。表面看这样会侵犯到C的区域，但实际上不要紧，因为在这个时候k绝对不会位于i的左侧，所以介于mi和i之间的这些元素，其实作为C中原来的元素必然已经归入到A中，当然是它的左侧在i之前的这部分中的某一个适当的位置。所以这种情况依然是安全的，无论是C[k]、还是B[j]转移到A[i]中去，都不会导致C中已有的元素被无意中覆盖掉，从而导致错误。

再来看最后两种更为复杂的情况，如图（c），B这个子向量已经提前耗尽，它其中的元素已经完全地归入到A中
当然也是就位了，而在C中还残存有部分的元素没有转移和就位。这种情况下我们的逻辑其实相当于等效地是在B的最右侧，就是lb这个位置上增加了一个哨兵节点，而且它的数值就是正无穷。因此即便C的右侧还残存有若干个元素它们也会在接下来的各次迭代中，因为是与这样一个正无穷相比而被认为是更小，从而顺利地转移到A中适当的位置，直到两个子向量都同时耗尽。

反过来另一种对称的情况（d）就是C也可能会提前耗尽，也相当于等效地 在C的最右侧增加了一个数值为正无穷的哨兵，它的秩是lc，所以即便在B的尾部 还残存有部分的元素也不要紧，它们也等效于和这样一个数值为正无穷的哨兵相比，总是会被认为是更小，所以按照算法的逻辑会等效地转移到A中剩余的对应区域中去，整个这个过程也是会顺利地进行，不会出现我们所说的数据遗漏或者数据被无意中覆盖。

需要注意的是（c）和（d）这两种情况其实并不对等，因为按照这里的设计，其实向量C和B地位本来就是不等的。B是完全复制出来的一个缓冲部分，而C虽然是独立的绘制出来但实际上它就在A中，占据右端，换而言之如果是C提前耗尽，我们确实需要把B尾部的这些元素悉数转移到A的尾部，但如果是B提前耗尽那么对C尾部这些元素的转移其实都是多余的，因为它们原来就在那，完全没有必要。注意到这样一个现象的话，我们就不难对刚才表面上很规范的逻辑进一步的精简：

1
2
3
4
5
6
for (Rank i = 0, j = 0, k = 0; j < lb; ) {
	  if ( lc <= k || (B[j] <= C[k]) ) 
          A[i++] = B[j++];                          //B更小，C[k]已无或不小
	  if ((k < lc) && (C[k] <  B[j]) ) 
          A[i++] = C[k++];                          //C更小，或B[j]已无或更大
  }

这里最重要的改进就是并不需要考虑C提前耗尽的那种情况，我们只需要考虑B提前耗尽的情况，一旦B提前耗尽
我们就可以直接终止这个循环包括这个算法，这样可以使这个算法效率进一步的提高，尽管不是从渐进角度而言的一种实质的提高。

那么这个算法在原来以及包括这样精简之后，从渐进意义上讲 复杂度是多少呢？是否能像我们最初所预期的那样能够有大幅度的提高呢？

复杂度

  • 算法的运行时间主要消耗于for循环，共有两个控制变量

    ​ 初始：j = 0, k = 0

    ​ 最终：j = lb, k = lc

    ​ 亦即：j + k = lb + lc =hi - lo = n

  • 观察：每经过一次迭代，j和k中至少有一个会加一（j + k 也至少加一）

  • 故知：merge()总体迭代不过$O(n)$次，累计只需线性时间

    这一结论与排序算法的$\Omega(nlogn)$下界并不矛盾——毕竟这里的B和C均已各自有序

  • 归并算法在最坏情况下的复杂度：$T(n)=2\cdot T(n/2)+O(n)$ ——>$T(n)=O(nlogn)$

  • 注意：待归并子序列不必等长

    亦即：允许lb $\ne$ lc，mi $\ne$ (lo + hi) / 2

  • 实际上，这一算法及结论也适用于另一类序列——列表