9. 归并排序概念¶

9.1. 归并排序概念¶

解决问题的一种自然方法是分治。在排序时运用分治，我们可以考虑把待排序的线性表拆成若干片段，分别处理，然后再以某种方式把它们重新组合起来。一个简单的做法是把线性表一分为二，对两半分别排序，再把排好序的两半归并起来。这就是归并排序背后的思想。

从概念上讲，归并排序是最简单的排序算法之一，无论是在渐近意义下还是在实验运行时间上都表现良好。遗憾的是，尽管它基于一个简单的概念，在实践中实现起来却相对困难。下面是归并排序的伪代码梗概:

List mergesort(List inlist) {
  if (inlist.length() <= 1) return inlist;; List L1 = inlist 中一半的项；List L2 = inlist 中另一半的项；return merge(mergesort(L1), mergesort(L2));
}

下面这个可视化演示了归并排序的工作原理。

归并排序中最难理解的一步是归并函数。归并函数先检查每个子线性表的首条记录，并挑出较小的值作为整体上最小的记录。这个较小的值从其子线性表中取出，放入输出线性表。归并就这样继续下去：比较各子线性表的首记录，不断把较小的那条追加到输出线性表，直到不再有输入记录为止。

下面是对线性表执行归并的伪代码:

List merge(List L1, List L2) {
  List answer = new List(); while (L1 != NULL || L2 != NULL) {
    if (L1 == NULL) { // 已完成 L1
      answer.append(L2); L2 = NULL;
    } else if (L2 == NULL) { // 已完成 L2
      answer.append(L1); L1 = NULL;
    } else if (L1.value() <= L2.value()) {
      answer.append(L1.value()); L1 = L1.next();
    } else {
      answer.append(L2.value()); L2 = L2.next();
    }
  } return answer;
}