一. 写在前面
要学习算法，“排序”是一个回避不了的重要话题，在分析完并查集算法和常用数据结构之后，今天我们终于可以走近排序算法这个大家族了。计算机科学发展到今天，已经有了成百上千种让你眼花缭乱，多的数不清的排序算法，而且还会有更新更厉害的算法尚未问世，它们都是人类无穷智慧的结晶，有太多太有意思的内容等待我们去思考，去品味。作为一篇入门级的学习笔记，我们不会在这里展开讨论，但是，我们将从“排序算法”这个百宝袋中，抓取几个经典的，脍炙人口的算法，作为这次我们讨论的主题。我们会先聊聊三种最基本的算法：选择，插入和Shell排序；然后我们走入分治思想的世界，聊聊归并排序；然后我们将登上世界之巅，来看看20世纪最伟大的算法之一——快速排序，了解一下这几十年来人们为了研究她都做了哪些巨大贡献；最后，我们将认识一个新朋友，一个为排序而生的数据结构——优先级队列，并以一些排序算法的实际应用作为本算法分析笔记的结束，在读完本篇文章之后，相信你会获得对排序算法有一个基础的了解。
当然，本篇文章介绍的内容都是我在学习Princeton大学Sedgewick教授的Coursera上公开课“Algorithms”时的一些心得，文章中的一些图示，例子和代码，均来自于老教授的课件和英文原版教科书，所有这一切的知识和成果，都是他老人家辛苦整理的智慧结晶。感谢Sedgewick老师，感谢这位可敬的老人带给我算法学习中的不少乐趣。
1.1 排序算法怎么玩
排序是一种将某元素的集合按照某种逻辑顺序进行排列的过程。我们之所以要排序，是因为它能满足我们的某种需要，特别是对于有强迫症的人来说，排列整齐总是比杂乱无章要好的。最简单的例子是，在前面介绍并查集算法时，我们曾经聊到过二叉搜索算法，它能很快地从集合中查找元素，但前提是该集合内的元素是已排序的。实际生活中的例子还有很多：比如人员名单在中国通常按笔画数排序，在英美国家则是字母顺序；学校里老师要按照分数对考试成绩进行排序，看看前十名都有哪些人；银行要按照资产情况对客户信息进行排序，存款最多的用户也许能发展成为该行的VIP客户；超市要按照时间顺序对交易记录进行排序，以打印账单等等。几乎所有需要用计算机去处理相关事务的领域，你都会看到排序算法的身影，它们往往是重要算法的关键一环。
1.2 排序算法的抽象设计
应用越广泛的东西，遇到的问题也就越多。如果我们只对简单的元素进行排序，那一点都不难，比如对数字进行排序，对字符串进行排序。但实际生活中我们往往要面对的是复杂的情况和复杂的对象。首先，不是所有的元素集合都能排序，比如我们爱玩的“石头剪刀布”游戏，石头干掉剪刀，剪刀干掉布，然后布又干掉石头，你把哪个放在前面都对，又都不对，无法排序；其次，对一个元素集合我们可能会按照多种标准进行排序，比如一条学生成绩记录可能包含姓名，学号，科目和分数等等，那我既可以按分数高低排序选出优秀学生，也可以按照姓名排序进行点名，更可以按照科目分数排序找出某一科的佼佼者。这些都会在实际生活中遇到，如何处理？
对于第一个问题，我们要先弄清楚的是究竟什么样的元素集合是可以排序的。答案是：如果你能在这个元素集合上找到一个“全序”（Total Order）关系，那么它就是可以排序的。全序的定义是：1）自反（Reflexive），对所有元素e，e=e都成立；2）反对称（Antisymmetric），对所有元素v和w，v < w则w > v，w = v则v = w；3）传递（Transitive），对所有的v，w和x，v <= w且w <= x，那么v <= x。“石头剪刀布”显然就不满足，因为虽然石头能干掉剪刀，剪刀能干掉布，但石头并不能干掉布，而是被布给干掉了，不满足传递性。不过在实际编程工作中我们也不用太在意，知道有这么回事就好，我们只需要通过某种方式告诉排序算法如何判断两个元素谁大谁小就可以了。
那么怎样告诉排序算法两个元素谁大谁小呢？我们的方法是基于“回调”机制实现，而各种不同的编程语言在“回调”的基础上建立了自己的处理方法：C语言使用函数指针，C++通过定义函对象重载函数调用操作符实现，Python语言通过FP的方式实现，Java语言和Go语言则是通过“接口”来实现。“面向接口编程”是一种重要的思想，在设计这种通用算法的时候就特别有用，这些通用的算法通过“回调”来处理具体的对象，而不需要知道对象的细节，这便是依赖倒置原则：细节依赖于抽象，而抽象并不依赖于细节。
在Java中，只要我们的类满足Comparable接口，通过实现compareTo()函数就能告诉排序算法两个元素谁大谁小。例如一个实现了Comparable接口的Date类如下所示，这样我们就可以用排序算法对Date进行按日期的排序排序。compareTo()函数返回一个整型来表示大小关系：正数表示大于，负数表示小于，0则表示等于。
public class Date implements Comparable<Date> {
/* ... */
public int compareTo(Date that) {
if (this.year < that.year) return -1;
if (this.year > that.year) return +1;
if (this.month < that.month) return -1;
if (this.month > that.month) return +1;
if (this.day < that.day) return -1;
if (this.day > that.day) return +1;
return 0;
}
/* ... */
}
除此之外，我们还要实现两个辅助函数：less和exch，less函数用于对元素的比较进行进一步“包装”——因为compareTo返回的是整型值，而我们需要一个返回布尔值的函数；exch函数则用于交换两个元素，这些都是排序算法中所需要的。这样，我们在实现排序算法时就通过这些函数，以一种统一的形式去操作数据结构，而不去关心它们是怎么比较大小或者怎么交换元素的。
private static boolean less(Comparable v, Comparable w) {
return (v.compareTo(w) < 0);
}
private static void exch(int[] a, int i, int j) {
int swap = a[i];
a[i] = a[j];
a[j] = swap;
}
那如果我们要对同一记录进行多种形式的排序又该怎么做呢？这就要用到Java的另一个更高级的接口——Comparator。这个接口只包含一个函数compare()，它同样通过返回一个整型值来表示大小关系：正数表示大于，负数表示小于，而0表示相等。比如我们有一个表示商业事务的类Transaction，包含客户姓名，日期和资产，我们需要对商业事务的记录按照姓名、日期和资产进行排序，那么我们就可以在Transaction中 实现三个满足Comparator接口的类：WhoOrder，WhenOrder以及HowMuchOrder。
import java.util.Arrays;
import java.util.Comparator;
public class Transaction implements Comparable<Transaction> {
private final String who; // customer
private final Date when; // date
private final double amount; // amount
/* ... */
/** * Compares two transactions by customer name. */
public static class WhoOrder implements Comparator<Transaction> {
public int compare(Transaction v, Transaction w) {
return v.who.compareTo(w.who);
}
}
/** * Compares two transactions by date. */
public static class WhenOrder implements Comparator<Transaction> {
public int compare(Transaction v, Transaction w) {
return v.when.compareTo(w.when);
}
}
/** * Compares two transactions by amount. */
public static class HowMuchOrder implements Comparator<Transaction> {
public int compare(Transaction v, Transaction w) {
if (v.amount < w.amount) return -1;
else if (v.amount > w.amount) return +1;
else return 0;
}
}
public static void main(String[] args) {
Transaction[] a = new Transaction[4];
a[0] = new Transaction("Turing 6/17/1990 644.08");
a[1] = new Transaction("Tarjan 3/26/2002 4121.85");
a[2] = new Transaction("Knuth 6/14/1999 288.34");
a[3] = new Transaction("Dijkstra 8/22/2007 2678.40");
StdOut.println("Unsorted");
for (int i = 0; i < a.length; i++)
StdOut.println(a[i]);
StdOut.println();
StdOut.println("Sort by date");
Arrays.sort(a, new Transaction.WhenOrder());
for (int i = 0; i < a.length; i++)
StdOut.println(a[i]);
StdOut.println();
StdOut.println("Sort by customer");
Arrays.sort(a, new Transaction.WhoOrder());
for (int i = 0; i < a.length; i++)
StdOut.println(a[i]);
StdOut.println();
StdOut.println("Sort by amount");
Arrays.sort(a, new Transaction.HowMuchOrder());
for (int i = 0; i < a.length; i++)
StdOut.println(a[i]);
StdOut.println();
}
}
相应地，less函数和exch函数也要做一些轻微的调整，如下所示。实际工作中，我们可以按照需求选择Comparable或者Comparator接口来设计我们的类。好了，以上就是我们为研究各种排序算法搭好的一个基本“框架”，我们介绍了Java的两个接口，介绍了回调机制以及“面向接口编程”的重要思想，下面，我们就来深入学习一下各种算法的思想及其实现吧。
// is v < w ?
private static boolean less(Comparator c, Object v, Object w) {
return (c.compare(v, w) < 0);
}
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}
二. 基础排序算法
我们以选择排序，插入排序和Shell排序为例，介绍三种最基本的排序算法。第一个要认识的就是选择排序算法，选择排序只能作为入门介绍，因为它糟糕的性能无法在实际生活中使用，而后两种算法就不同了，它们在一些特殊情况和场景下会很有用，这个后面会有讨论。
2.1 选择排序
用一句话来描述选择排序，就是把当前最小的元素放到它应该在的位置。算法会遍历序列中的每一个位置i，然后在i的右边选择一个（当前的）最小值，把它放到位置i，把位置i上原先存在的元素交换出去。算法第一次运行时，会把最小的元素放在位置0，第二次运行时把第二小的元素放在位置1……这样当遍历完最后一个元素时，整个序列就排好序了，如图2-1所示。
public class Selection {
// This class should not be instantiated.
private Selection() { }
public static void sort(Comparable[] a) {
int N = a.length;
for (int i = 0; i < N; i++)
{
int min = i;
for (int j = i+1; j < N; j++) {
if (less(a[j], a[min])) min = j;
}
exch(a, i, min);
assert isSorted(a, 0, i);
}
assert isSorted(a);
}
}
从上面的代码我们可以分析它的性能，算法总共的比较次数为(N-1) + (N-2) + ... + 1 + 0 = N(N-1)/2，交换次数为N次，故性能为O(N^2)。而且选择排序是一个“油盐不进”的排序算法，随便你给出什么样的输入序列——哪怕它已经是有序的——都需要平方时间才能完成排序，因此选择排序就跟冒泡排序一样，了解了解就好，没有什么实际的用处。
2.2 插入排序
插入排序名字取得不好，它应该叫“扑克排序”，想想你斗地主的时候是怎么理牌的，你就知道插入排序的大致步骤了。在插入排序运行的过程中，我们总是假定位置i之前已经是有序的，我们的任务就是将位置i的元素放到合适的位置，就好比摸了一张新牌，要把这张新牌插入到合适的位置一样。如图2-2所示，我们手里已经有了三张排好序的牌，当我们再摸到梅花3时，因为它比这几张牌都要小，所以我们最终将它插入到了最开始的位置。
public class Insertion {
// This class should not be instantiated.
private Insertion() { }
public static void sort(Comparable[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
exch(a, j, j-1);
}
assert isSorted(a, 0, i);
}
assert isSorted(a);
}
}
最坏情况下（输入序列逆序），待插入的元素要跟之前所有的元素相比较，因此需要N2/2次比较和交换；最好情况下（输入序列已排序），待插入元素无需移动，且只比较一次，总共需要N-1次比较；平均情况下，插入排序大概需要N2/4次比较和交换，因此它是一个O(N^2)的算法，遇到很大的序列，排序时间会比较慢。
但如果你就此下结论，说插入排序是一个没用的算法，那就太轻率了。插入排序有一些很有趣的性质，科学家们对插入排序更进一步的研究发现，插入排序对较小的序列很有效，而且对部分有序的序列效率很高。要理解部分有序，首先要认识一个“逆”的 概念，一个序列中的“逆”，是指序列中的逆序对，比如“A E E L M O T R X P S”中“T-R T-P T-S R-P X-P X-S”就是其中存在的6个逆。若一个序列元素有N个，则“部分有序”是指该序列的逆序数小于等于cN，其中c为常数。
如果一个序列是部分有序的，那么插入排序的运行效率将会是线性的，即O(N)时间内就能完成，为什么呢？仔细观察插入排序的代码你就会发现，每进行一次交换，序列的逆序数就会减一（因此插入排序可以用来计算一个序列的逆序数，归并排序也能），因此交换的次数就等于逆序数，既然逆序数小于等于cN，那么交换的性能为O(N)；关键在于比较的次数，首先，每个元素至少都要跟它前面的那个元素进行一次比较，所以一定有(N-1)次，其次，每发生一次交换就意味着有过一次比较，且比较的结果是该元素比它之前的那个元素小，因此总的比较次数一定是(N-1)再加上交换的次数，比较的性能仍然是O(N)，所以在面对部分有序的序列时，插入排序能做到线性时间内完成。
这一事实导致了两个有趣的结果。首先，你会发现插入排序总是跟归并排序和快速排序算法玩“暧昧”，在归并排序和快速排序将序列分解成一定规模的小数组之后，使用插入排序对这些小数组进行排序要比继续分解要好，能够节省一些开销，如图2-3和2-4所示。在1993年Bentley 和 McIlroy那篇著名的论文“Engineering a Sort Function”中，两位大神给出了一种具有实际工程意义的快速排序实现，该算法在处理较小的数组时，就使用了插入排序。时至今日，该论文已经成为各种编程语言排序算法标准库实现的必备参考，你如果有心去阅读这些语言的源代码，就能发现该论文的身影。比如Go语言sort包中快速排序的实现就借鉴了该论文的思想，如图2-5和2-6所示。
另一个有趣的结果是，因为插入排序对部分有序的数组工作的很好，科学家们就挖空心思地钻研如何将序列弄得部分有序，这诞生了另一个有趣的算法——Shell排序，你可以将Shell排序当成插入排序的一个变种，这也是我们接下来要分析的。
2.3 Shell排序
如上所述，Shell排序是对插入排序的一种改进。既然插入排序对部分有序的序列很有效，那么我们就要琢磨一下怎样让序列变得部分有序。Shell排序的思路是，与其像插入排序那样挨个排序，还不如间隔h个元素进行排序，也就是每次排序向前跳h个位置，这样序列虽然整体上看貌似无序，但每间隔h个元素的序列却是交错有序的，这种排序被称为h-排序，而排序后的序列被称为“h-有序的”，如图2-7所示。Shell排序有个重要的概念，一个h-有序的序列在g-排序后仍然是h-有序的，那么如果我们以某种方式逐步缩小h直到h变为1，那么当进行h为1的那次排序时，序列已经部分有序，而且排序也退化为一般的插入排序，那么算法的执行效率也就有了提高。在一开始时，因为h很大，所以子序列很短，随着算法的进行，h越来越小，子序列越来越长，整个序列部分有序的程度越来越高，执行插入排序的效率也就越来越高。那么h的跳数该怎么选择呢？人们已经找到不少有效的计算公式，但一个简单实用的“3X+1”即可满足绝大部分的性能要求了。
public class Shell {
// This class should not be instantiated.
private Shell() { }
public static void sort(Comparable[] a) {
int N = a.length;
// 3x+1 increment sequence: 1, 4, 13, 40, 121, 364, 1093, ...
int h = 1;
while (h < N/3) h = 3*h + 1;
while (h >= 1)
{
// h-sort the array
for (int i = h; i < N; i++) {
for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
exch(a, j, j-h);
}
}
h /= 3;
}
assert isSorted(a);
}
}
首先，我们让h增大到大约N/3的位置，然后一边对序列进行h排序，一边减小h的值，每次减小到原来的1/3，这样最后一次h的值就为1，有科学家研究，该算法最坏情况下的运行效率为O(N^3/2)，算法演示如图2-8所示。Shell排序是一个颇具神秘魅力的算法，因为对它的平均情况效率还没有得出可用的结论。但这并不妨碍Shell排序成为一个实用的算法。除非遇到巨大的序列，Shell排序还是很快的，在嵌入式和硬件领域应用较为广泛。
2.4 随机洗牌算法
大多数时候，我们希望得到的信息是排列有序，让人赏心悦目的，但有些时候我们却希望信息是乱序的，是随机的，是让人猜不准下一步会得到什么的。比如你在网上开了一家虚拟赌场，让大家都来你这里打牌斗地主，你就希望洗牌算法每次得到的结果都不一样，否则每次拿到一样的牌，这地主还怎么斗下去呢，这也不符合实际情况呀。所以我们的目标是：重新排列数组，使得得到的排列是均匀分布的。其中的一种办法是，我们为数组中的每一个位置用满足均匀分布的伪随机数生成器产生一个随机数，对随机数进行排序，就能得到想要的结果（当然，举一反三地想想，如果我们使用产生满足其他概率分布的随机数生成器，就能生成满足其他性质的随机序列），如图2-9所示。
还有一种随机洗牌算法更常用，是牛人Knuth他老人家发明的，叫做Knuth Shuffle，这种方法的基本思想就是：对于元素arr[i]，用随机挑选的另一个元素arr[r]与它进行互换，其中r是[0, i]或者[i, N-1]区间内随机选出来的一个元素，如下所示。
public static void shuffle(Object[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
int r = StdRandom.uniform(i + 1);
exch(a, i, r);
}
}
public static void shuffle(int[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
int r = i + uniform(N-i); // between i and N-1
int temp = a[i];
a[i] = a[r];
a[r] = temp;
}
}
实际上，开发随机数算法一定要慎之又慎，因为稍不注意就会出现一些很小的漏洞，如果在线扑克牌游戏中出现这样那样的一些漏洞，黑客就可以利用它推算出程序将要发什么牌，这有时候是灾难性的，网上有一篇著名的博文当随机不够随机：一个在线扑克游戏的教训就介绍了上世纪90年代末国外一个很流行的在线扑克平台出现过的严重错误，是随机洗牌算法的一个很好的反面教材，提醒我们算法设计一定要小心，有兴趣的可以看一看。
三. 算法名人堂——归并排序
基本排序介绍完了，现在我们登堂入室，来认识一个家喻户晓的著名算法——归并排序。不像Shell排序，人们对归并排序的性能可谓了如指掌，所以她被大量运用到各种计算系统中。Java就用她来排序各种对象，而C++和Python等编程语言则使用她来实现一种“稳定”的排序算法，我们对归并排序的介绍，就从“稳定性”这个概念开始。
3.1 排序算法的稳定性
“稳定性”是在对记录进行多种方式排序时通常要考虑的问题，如果记录可以通过Key1排序，又可以通过Key2排序，那么在Key2排序之后，如果Key2相同的一众记录相对于Key1而言仍然是有序的，那么我们就说该排序算法是稳定排序，否则，就是不稳定的，图3-1中所示的例子中，我们先对学生记录按照姓名进行排序，然后又按照分区进行排序，结果第3区的学生不再是按姓名排序的，因此选择排序并不是一个稳定的算法。在我们介绍过的算法中，只有插入排序是稳定的，因为它每次移动元素的跨度很小，不会跑到跟它一样大的元素前面去。而选择排序和Shell排序跨度都比较大，比如Shell排序一开始就每间隔h个元素进行排序，自然无法保证稳定性。
归并排序不但效率最优，而且满足稳定性，是一个优秀的算法。它的基本思想就是将序列一分为二，分别排序左半部分和右半部分，然后再将这两部分归并成一个有序的序列，其中对左半部分和右半部分的排序是递归的，仍然是一分为二然后归并，如图3-2所示。归并排序就是一个很典型的“分治”算法思想的体现：某问题解决起来困难，那么我们就将该问题不断拆分成众多子问题，然后将子问题的解汇总成最终问题的解。“分治”算法不但高效且容易进行数学分析，这个后面会看到。
3.2 归并排序中的归并
如图3-3所示，在归并排序中，归并是一个重要的组成部分，它的基本思想是：拷贝并使用一个同样大小的辅助序列aux，用两个索引分别指向已排序的子序列aux[lo..mid]和aux[mid+1..hi]，同时遍历两个序列，比较遍历到的元素，每次都将最小的元素放入arr，如果其中有哪个子序列归并完了，那么就将另一子序列的元素一个一个拷进去。使用辅助数组aux意味着这种归并排序的空间效率不高——每次都要使用额外的O(N)空间，其实归并排序的版本不止一种，还有一些比较复杂的算法实现了真正的就地归并。这里还可以学到一个新技能：断言。通常每个算法的执行都会有一个前置状态（Precondition），当满足前置条件时执行该算法才是正确的，而算法正确执行之后总会带来某种状态的改变，称为后置状态（Postcondition），比如归并，前置状态要求两个子序列是排序的，后置状态要求整个序列是排序的，很多语言都提供了大同小异断言机制，比如Java的assert指令，并提供了激活断言的开关功能。那么我们就可以在代码中使用断言，这至少有两个好处，首先断言能够尽可能早地发现程序中出现的潜在问题，提醒开发者代码执行的条件没有被满足；其次，它是一种文档，明确地告知了算法执行的先决条件和带来的改变，能够提高代码的易读性。
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
assert isSorted(a, lo, mid);
assert isSorted(a, mid+1, hi);
// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++]; // this copying is unnecessary
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
// postcondition: a[lo .. hi] is sorted
assert isSorted(a, lo, hi);
}
3.3 各个击破：自顶向下的归并
有了归并，排序就被设计为一个递归的过程：每次都计算一个中间位置mid，然后递归地排序左右两部分，最后归并排序好的子序列，当hi <= lo时递归返回，因为此时子序列中没有元素，不需要做任何操作，代码如下所示。因为sort是递归调用，因此每个sort调用都会包含自己的merge过程，也就保证了子序列在归并前已经是有序的了。归并排序是一个速度很快的算法，有科学家做过经验分析，通过实验分别在家用计算机和超级计算机上对比了她与插入排序的运行效率，得到如图3-4所示的实验结果，可以看到即使是百万级的记录归并排序仍然是瞬间完成，插入排序却需要等上300多年。
// mergesort a[lo..hi] using auxiliary array aux[lo..hi]
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid + 1, hi);
merge(a, aux, lo, mid, hi);
}
对归并排序的数学分析代表了对“分治”这一类算法进行分析的基本模式，掌握了这种分析方法，当我们面对各种分治算法时我们就可以用同样的方法去分析它们的效率。分治算法的效率分析通常可以通过解某一递推公式来完成，就归并排序而言，因为我们每次都将序列一分为二排序后进行归并，如果我们假设C(N)为算法对长度为N的序列进行排序所需比较次数，那么我们可以得到如图3-5所示的递推公式。解这个递推公式可以得到归并排序的效率为NlgN，具体的推导过程这里就不赘述了，《算法导论》这本书上有全面而详细的指导。这里只给出一个比较直观的解释，如图3-6所示。假设N为2的幂，我们可以将归并排序一分为二的过程看成一棵树，这棵树每一层都有N个结点，它会一直分解，而树的高度为lgN，所以最后得到NlgN。
3.4 积少成多：自底向上的归并
自顶向下的方法通常都存在着一个对称的逆过程，有时候我们也可以反过来想，用自底向上的思路去解决问题。前面提到，长度为1的序列是天然有序的。那么我们可以多遍历几次，第一次将长度为1的子序列归并为有序的2-序列，然后将有序的2-序列归并为4-序列……这样反复进行下去，直到整个序列都归并为有序的，这样连递归都不用了，两层循环就能搞定。说起来简单，但要真正实现的话，一些细微的地方要注意。从下面的代码示例可以看到，外层循环从1开始，每次加倍，因为第一次要处理大小为1的序列，第二次要处理大小为2的序列，第三次则是大小为4的，以此类推。然后在每一次循环的内部，用索引i来记录每次要处理的序列头部（一次迭代跳过sz+sz个元素）。我们分别计算lo，m和hi，使得aux[lo..m]和aux[m+1..hi]为两个相等长度的待归并子序列，然后仍然用上面提到的归并方法进行处理。
public static void sort(Comparable[] a) {
int N = a.length;
Comparable[] aux = new Comparable[N];
for (int sz = 1; sz < N; sz = sz+sz) {
for (int i = 0; i < N-sz; i += sz+sz) {
int lo = i;
int m = i+sz-1;
int hi = Math.min(i+sz+sz-1, N-1);
merge(a, aux, lo, m, hi);
}
}
assert isSorted(a);
}
3.5 基于比较的排序算法，其极限何在？
我们已经分析过的选择排序，插入排序，Shell排序和归并排序，以及下面会谈到的快速排序，都可以看作是一类排序算法——基于比较的排序算法，也就是说，它们只知道元素之间的大小关系，其他的信息（比如是否有重复元素，是否部分有序等等）则完全不知。对于这一类算法，我们可以通过一种叫“决策树”的工具，得到一个计算复杂度方面的重要结论。图3-7展示了对三个不同元素a，b和c的排序过程。从根节点到某一叶子结点的路径表示某次排序的比较序列，叶子结点表示最后得到的结果。首先，对于N个不同元素的排序决策树，至少有N！个叶子结点，因为有N！种排列的可能。其次，二叉树有一个重要的性质，即高度为h的二叉树最多有2h个叶子结点。故得到公式2h >= #leaf >= N!，即h >= lgN! >= NlgN（根据斯特林公式得到）。也就是说，我们对基于比较的排序算法建立的决策树模型，其高度至少是NlgN，而树的高度表示算法最大比较次数，那么我们就能得出一个结论：最坏情况下所有基于比较的排序算法至少要用NlgN次比较。
要注意，这是一个很重要的结论。从这个结论，我们可以得出这样一个事实：归并排序是时间最优的，因为它最坏情况下比较次数为NlgN。其次，不可能找到比较次数比这个还少的算法——因为这违反客观规律了，但是，这个结论同时启发我们，应该可以找到时间是NlgN，但空间效率更优的算法，可以从这个方向去想。另外一个细微之处在于，该结论依据的基本假设条件是该序列是由N个不同的元素组成的，若序列中出现重复元素，或该序列是部分有序的，那么算法的效率会比NlgN还要高。使用某个结论之前要考虑该结论成立的条件是否满足，否则会闹笑话的。
