有诗言：“横向项目无人理，快排不会冒泡替”。这个故事告诉我们，一定要学会排序算法。除此以外，排序本身虽然不难，但各种排序算法体现了近乎所有的程序设计思路。
实际上互联网上有许多充分的，各种排序的教程和学习笔记。我很难写出什么新意，我只是记录一遍作为记忆。下面讨论的排序都是内部排序，即我们关注于排序本身。
排序可以定义为，对于包含了$n$个记录的序列$\left\{ R_1,R_2,…,R_n \right\} $，其对应的关键字序列为$\left\{ k_1,k_2,…,k_n \right\} $。用有限的操作将这$n$个记录重排为$\left\{ R_{p1},R_{p2},…,R_{pn} \right\} $，使其关键字满足$k_{p1}\le k_{p2}\le …\le k_{pn}$或$k_{p1}\ge k_{p2}\ge …\ge k_{pn}$。由于关键字之间可能相等，例如对于$R_i$和$R_j$，有$k_i=k_j$，如果排序后，$R_i$和$R_j$的相对位置发生了变化，那我们称这种排序是不稳定的，反之则是稳定的。
上述定义很符合事实，因为我们往往都是对一个事物的特定属性来排序，比如一个班里所有同学的身高。这里名字就是$R_i$，身高的值就是$k_i$。所以在下面的排序中，我们操作这样的结构体：
1 | typedef int datatype; |
如果我们要排序$n$个元素，那么我们往往会开辟一个$n+1$的数组，数组里的每一个元素为rectype。第0号元素是“哨兵单元”，如果不需要“哨兵单元”，那么第0号元素就是空的。“哨兵单元”可以免去判断边界条件，也叫“监视哨”（Sentinel value）。在另外一些时候，“哨兵单元”是用来备份当前在操作的值，因为在一些过程中，被操作的值可能被覆盖掉。
Insert Sort
直接插入排序，是将序列分成有序区和无序区，然后将无序区的元素依次与有序区的元素进行比较，插入进有序区。
1 | void InsertSort(rectype R[]) |
在直接插入排序中，我们清晰的看到的哨兵单元的作用。①哨兵单元储存了当前要排序的$R[i]$，因为在第二层循环，寻找插入位置时，$R[i]$会被覆盖。②在第二层循环的条件中，省去了边界判断$j>0$，因为$R[0].key$总等于自身。
我们可以从动图中看出插入排序的特点：基于比较，数据移动完成排序，一次比较操作后不发生数据移动或仅仅交换一对相邻的数据元素。
粗略来看，当序列本身有序时，时间复杂度为$O(n)$；序列为逆序时，时间复杂度为$O(n^2)$。
在最好的情况时，第二个子循环根本不会被执行，因为$R[i].key$一定大于$R[i-1].key$。所以整个序列只会被线性搜索一次，为$O(n)$；最糟糕时，需要循环到最左边才能找到插入的位置，当处理第$R[i]$时，需要循环$i$次。所以：
此时时间复杂度即为$O(n^2)$。在平均情况下，我们可以粗略地认为每次插入的位置在有序区的中间，所以此时需要循环的次数为最糟糕时的二分之一，即$n^2/4$，仍是$O(n^2)$。
由于最后的插入过程，完全是一个先查找，再移动的过程。而且查到的是一个有序的序列，所以我们可以用二分来优化这个过程。即折半插入排序。
1 | void BinInsertSort(rectype R[]) |
然而，这种优化方式只减少了关键字的比较次数，而没有减少移动次数。实际上，我们可以测一下排序$n=100000$和$n=200000$个数据，记录一下时间：
| n\time(s) | InsertSort() | BinInsertSort() |
|---|---|---|
| $n=100000$ | 5.435 | 4.697 |
| $n=200000$ | 21.3752 | 18.9099 |
可以发现，速度快了一些，但整体上还是$O(n^2)$。这是由于插入排序的操作实际上有两个：比较(comparisons)和赋值(assignments)。赋值也就是移动。严格来说，我们需要分析这两种操作各自的时间复杂度，我们一般所说时间复杂度，关心的是这其中性能最差的那个。在后面与别的排序算法对比时，这其中的差异会体现出来，但现在我们先不用考虑这么多。
实际上，这两种操作的在插入排序中的平均时间复杂度都是$O(n^2)$，而用二分查找来优化比较，并不影响移动的时间复杂度，所以导致整体还是$O(n^2)$。推导这里就从略了。这种最后不影响大$O$的优化，叫常数级优化。
接下来，我们从一个high-level的角度上，探索插入排序是否还可以被进一步优化。在一个序列中，如果$a[i]>a[j]$且$i<j$，我们称其为一个逆序对（因为我们的目的是升序排列一个数组）。排序算法，就是基于元素比较，来消除一个序列的逆序对，而且一次最多消除一个。
一个有$n$个元素的序列，共有$n!$种排列方式。在最糟糕的情况下（完全逆序），序列会有$n(n-1)/2$个逆序，不失一般性，我们构造一个与此完全相反的序列，它没有逆序对。所以平均会有$n(n-1)/4$个逆序。这就导致，它确实不能再优化了。这是这种基于比较的插入策略所决定的。
Shell Sort
我们知道，如果对于几乎排好序的序列，应用插入排序可以得到近似$O(n)$的效率。同时，插入排序的一大瓶颈在于，它的一个操作只能将数据移动一位（$R[j+1]=R[j]$）
希尔排序作为插入排序的一个优化，它是先对原序列进行特定步长的采样，然后对采样出的子序列，进行一次插入排序。之后逐渐缩小步长，在最后步长一定等于1，这就导致在最后一定会用一次普通的插入排序来保证数据一定有序。
1 | void ShellSort(rectype R[], int d[], int t) |
我们一般采取$n/2^i$来作为步长，比如$n=10000$的话，最开始的步长是$5000$，然后$2500$，最终到1。
希尔排序的时间复杂度的分析比较困难，我们只需要知道，由于增量序列选择不同，希尔排序的复杂度在$O(n\mathrm{log}n)$到$O(n^2)$之间；当$n$达到某特定范围时，时间复杂度为$O(n^{1.3})$。
实际上，希尔排序与插入排序相比，它是先整体地对待整个序列，使其相对有序，最后再整体有序。而插入排序是令有序区严格的有序。这两者之间体现了通过减少递归深度来使其尽快达到递归边界的思想。也就是分治法(divide and conquer)，我们在后面的几种排序中也会遇到这种思想。
Bubble Sort
冒泡排序是大一学到的第一种排序。它的原理非常简单，线性的走访待排序的序列，依次比较相邻的两个元素。如果它们是降序，那就交换位置。然后不断的重复走访。它之所以叫冒泡排序，是因为通过一次这样的走访，走能把最大（最小）的元素浮动到序列末尾（头部）。
所以，这是一种基于交换的排序。
1 | void BubbleSort(rectype R[]) |
朴素的冒泡排序，无论对于已排好序的序列还是完全的逆序列，都表现出$O(n^2)$。一个很简单的改进是标记一个交换标志：
1 | void BubbleSort(rectype R[]) |
这样，对于近似排好序的序列，就可以达到$O(n)$。
除此以外，我们还有类似的常数级优化，①双向冒泡—鸡尾酒排序，②记录最后一次标志位。
我们观察整个冒泡的过程，在我们的写法里，一次扫描就可以把最大的元素送到末尾，而最轻的元素只能上升一次。这就导致对于一些序列和它们的对称序列，需要扫描的趟数会完全不同。所以就有了鸡尾酒排序，鸡尾酒排序即从左到右排一次后，再从右到左排一次：
1 | void CocktailSort(rectype R[]) { |
记录最后一次标志位，是考虑到，在最后一次交换的右侧（由扫描方向的不同，也可能是左侧）序列是有序的，所以没必要扫描那里，扫描可以提前终止：
1 | void BubbleSort_last(rectype R[]) { |
我们可以把这三个优化组会在一起，得到最终版的冒泡排序：
1 | void Bubble_Sort_optim(rectype R[]){ |
现在，比较一下耗时！
| n\time(s) | BubbleSort | +swap | +Cocktail | +last | +all |
|---|---|---|---|---|---|
| $n=10000$ | 0.204067 | 0.214467 | 0.165133 | 0.207400 | 0.152267 |
| $n=20000$ | 0.908000 | 0.871333 | 0.670200 | 0.956800 | 0.619333 |
| $n=30000$ | 2.228467 | 2.234400 | 1.680400 | 2.180133 | 1.506467 |
由于上述序列是生成的随机序列，所以在近似排好序时的优势没有很好的体现出来。
不管再怎么优化，冒泡排序都是$O(n^2)$的。然而我们仍然可以用基于分治的思想来写出更高效的排序算法。
Quick Sort
与将插入排序优化为希尔排序类似，快速排序是堆冒泡排序的一种改进。相比于冒泡排序每次严格的让一个最大值（最小值）移动到末尾（开头），快速排序是通过一趟排序，让序列整体有序。
首先，它从序列$R[1]\sim R[n]$中任选一个记录$R[p]$作为基准(pivot)，比基准小的，就安排在其左边；大的就安排在其右边。然后原来的序列就被分为了两个子序列，之后递归的执行这个操作。每一次，算法所处理的规模都得到了缩小。当划分的子序列左右只含1个或0个元素时，序列就是有序的了。
将序列划分为子序列，其实是个很有名的操作，即划分(partition)。它甚至比快排本身还有名。
1 | int Partition(rectype R[], int low, int high) |
上面的划分函数中，我们先选取序列最末端的那个元素作为基准，然后使用两个指针low和high进行双向扫描。例如考虑序列$[1, 5, 3, 7, 4]$：
1 | pivot: 4 |
一个很好的性质是：这个划分算法是原地的。在后面分析空间复杂度时，我们会意识到这一点的优越性。
然后，我们只需要递归的进行这个划分，然后对每个划分的子序列进行排序即可：
1 | void QuickSort(rectype R[], int s, int t) |
仔细观察动图，我们会发现一个现象。如果序列是基本有序的，那么每一次分成的两个子序列的长度会相差很大。比如选pivot为末尾的关键字，然而此时序列基本有序，末尾的关键字基本就是最大的。这导致划分出的序列和没划分一样：
此时，总的比较次数为：
此时，彻底退化为了冒泡排序。
在最好的情形下，每次划分，序列都被划分为长度相等的两份。假设序列长度是$n=2^k$，这样会便于推导。那么对长度为$n$的序列作快速排序需要比较的次数$C(n)$可以写作：
其中，$C(1)$是一个常数。$C_p(n)$是一次划分所需比较的次数，我们知道划分过程是一个线性序列的双向扫描，是拿出一个关键字，与剩下的关键字作比较。所以$C_p(n)=a\cdot n$，这里$a$是个常数。不失一般性，我们把这些常数都设成1，可以得到：
有人可能会说：划分时明明是比较了$n-1$次。这其实是影响低阶项，为了简洁就按$n$处理了。
然后，有了一个不显然的问题。在前面的排序中，我们可以用逆序对的思想进行分析，得到他们平均时间复杂度也是$O(n^2)$（希尔排序除外，它很特殊）。那么快速排序的平均时间复杂度是多少呢？那样，我们就需要把上面最优情况的式子一般化了，由于划分是等概率的：
然后，我们就有了一个非常熟悉的形式……似曾相识，如果我们把$C(i)$写成$a_n$，那么右边就是$S_{n-1}$了。我们应用错位相减：
分子分母同除$n(n+1)$：
裂项相消：
我们发现两侧有了明显的递推的形式：
由调和级数：
最后$C(n)$渐进于$2n\ln n$，换底公式置换一个常数：
即$1.39n\mathrm{log}n$。所以，快速排序的平均时间复杂度仍是$O(n\mathrm{log}n)$。
这说明，快速排序确实是一种性质独特的排序。我们也很好分析它所需要的空间复杂度，由于我们使用的是原地划分，所以在每次调用前，都只是$O(1)$的，它只会使用固定的额外空间。然而，最好情况下，需要$O(\mathrm{log}n)$次的递归调用，最坏情况下则是$O(n)$。从这里可以看出，快速排序是二叉搜索树的一个空间优化版本。二叉搜索树是循环的将数据插入一颗明确的树中，而快速排序是组织这些数据到一个递归调用所隐含的递归树里。
写到这里，其实我们已经对快速排序有了足够的了解。但仍然有一些小的事宜没有阐述。
一、pivot的选取。虽然快速排序的平均时间复杂度是$O(n\mathrm{log}n)$，但我们还是没有给出在最坏情况下的优化。这里介绍两种：随机pivot和三者取中。
随机pivot也即随机快速排序，它忠实的施行推导时间复杂度时的条件—随机分割。
1 | template <typename T> |
除了用随机数来shake，还可以“三者取中”，即R[low].key，R[high].key与R[(low+high)/2].key作比较，三者取中间的这个数：
1 | int GetMid(rectype R[], int left, int right) |
二、划分算法partition，我们之前都是双向扫描i的。这其实会带来一个问题，截止到目前位置，我们都在自由地讨论一个可以随机访问的数组的排序。然而像链表，它并不支持这样的功能，链表排序应用最多的算法叫作归并排序，这个我们在后面会继续介绍。我们现在重点关注，如果在类似的情形下，我们要被迫的单向扫描，然后来原地分割，应该怎么实现。
单向扫描的核心在于，比如我们从左至右扫描，我们只要维护“左侧”的元素始终比pivot小，如果左侧有比pivot大的，那么就把它和右侧的交换。这样就维护了一侧比pivot小，另一侧比pivot大。最后再把pivot本身（如果我们选择的是最右边作为pivot）替换到边界上，任务就完成了。
1 | int Partition_One_Way(rectype R[], int low, int high) |
我们以$[1, 9, 3, 6, 5, 4]$来模拟一下单向扫描的过程：
1 | pivot: 4 |
三、相等**。**我们之前讨论最坏情况时，是延续之前分析的思路—有序，逆序。然而在这种基于划分的方法中，还会有一种情况：相等。在这种情况下，每次划分出的序列就可能导致极度的不平衡，例如：
1 | R. |
此时，15都被分到了右侧。
解决这一点需要用所谓的“三路快排(Quick Sort 3 Ways)”。即我们在划分时，把这些15都聚在一个中间的区间里，然后确定这个区间的边界。则剩下的两路，即小于15和大于15的，序列长度就会大大减少，提高排序的效率。
注意的是，我们先前并不会知道15是最合适的pivot。但如果15真的重复的次数很多的话，比如100个关键字里有80个都是15，那么大概率，你会随机抽取到，或者第一个和最后一个元素就是15。
此时的partition的写法，其实是刚才单向扫描的扩展：
1 | void Partition_three_ways(rectype R[], int low, int high, int res[]) |
我们结合一个具体的序列来看一下此时的partition，此时我们维护了3个指针：i,lt,gt：
1 | pivot: 2 |
与之前的单向扫描的写法相比，i不在固定的小于high，而是小于gt。gt的移动性带来了另一个区间。
我们可以测试一下这个partition：
1 | R |
可以发现，这样下来，能节省大量无意义的序列长度。
四、递归改成循环。之前我们实现的快排函数都是基于函数递归调用的，我们还需要了解，如何把递归的快排，改成非递归的。即用栈来模拟这一过程。
1 |
|
实际上，非递归的快排非常好理解。因为快排，实际上排序是在partition中进行的。我们只需要用栈记录每个时候的边界即可。当栈空的时候，快排自然就排完了。我们打印出了在一个例子下，stack里的内容的动态变化：
1 | before sorting. |
可以看见，最开始输入序列索引1和8（即整个序列）。然后选择了7为基准以后，分为了一个只有一个数字的序列(8|8，第一个8是r+1的缘故)和一个1|6的序列(6是因为r-1)。通过不断的划分。最后栈顶开始不满足low<high。于是开始纷纷出栈。
行文至此，我们可以发现，快速排序的精髓在于：partition。实际上，各种partition也是有些算法题的解法。现在我们开始进行一些小型的测试，观察这几种不同的快排变种有怎样的效果：
| random | Quick Sort | Random | Mid | Three Ways | No Recursive |
|---|---|---|---|---|---|
| $n=1000000$ | 0.139550 | 0.126667 | 0.120100 | 0.184167 | 0.172700 |
| $n=2000000$ | 0.299200 | 0.274500 | 0.260133 | 0.386933 | 0.358967 |
| $n=3000000$ | 0.467700 | 0.422433 | 0.395067 | 0.601633 | 0.565467 |
| almost order | Quick Sort | Random | Mid | Three Ways | No Recursive |
|---|---|---|---|---|---|
| $n=1000000$ | >10 | 0.106200 | 0.042267 | >1 | >10 |
| $n=2000000$ | >10 | 0.311033 | 0.085833 | >1 | >10 |
| $n=3000000$ | >10 | 0.623767 | 0.131967 | >1 | >10 |
| more equal | Quick Sort | Random | Mid | Three Ways | No Recursive |
|---|---|---|---|---|---|
| $n=1000000$ | >10 | >10 | >10 | 0.104433 | >10 |
| $n=2000000$ | >10 | >10 | >10 | 0.217867 | >10 |
| $n=3000000$ | >10 | >10 | >10 | 0.338233 | >10 |
可以看到，在平均情况下，性能的差别由一些常数级的复杂度影响，有一些轻微的变化。当处理到如近似有序和有许多相等键值时，没有针对性优化的快排算法退化的非常严重。如果是单纯随机生成的数据，那么影响不会很大。可是大部分时候要排序的数据总是符合一定规律的，这就导致了我们需要在不同的情景下切换不同的算法。
最后值得注意的一点是，我们使用STL模板类实现的栈模拟快排，性能会相对递归的下降一些。这其实是STL模板类里的栈的问题，一般来说自己手动实现一个栈，效率就会得到改善。提到这里，还有一个很小的点，是关于减少递归调用时的内存消耗的。我们以递归式为例，当每一次递归调用时，都会在内存的栈区存放一个函数栈帧，上面记录着函数的参数，局部变量和返回地址等信息。就像非递归时每一次栈上会多出2或4个元素，或者不变一样。当序列长度特别长时，调用次数会指数增加。而只有在分成0或1个子序列时，才会开始return。所以一个用来减少内存消耗的办法，是在序列长度被分割到很小的时候，比如10个以内，改用普通的插入排序。这种做法叫作小区间优化。
“我们学的不是排序，是partition。”
Select Sort
经历了快排以后，再来看选择排序，我们会觉得非常轻松和简单。实际上，选择排序的思想很简单：我每次都挑出这里最小或最大的，然后把它拿出去，继续再挑一轮。
1 | void SelectSort(rectype R[]) |
我们容易分析出这种排序的时间复杂度为$O(n^2)$，并且它也没有什么最好情况最坏情况之分。这种算法体现了贪心策略，即每步我都只选当下最好的解。
然而，这种排序其实并没有很好的利用每次比较的结果。比如在第$n$次比较时所要做的判断，可能在前面已经判断过了。基于这一点，就有了堆排序。
Heap Sort
堆排序是选择排序的一种改进，它将储存的记录借助一个完全二叉树的顺序结构来进行存储。这种结构称为堆。但这个过程远远没有平衡二叉树那么令人头疼，实际上你如果乐意，你完全可以把它看成“基于先验的对数组元素进行交换”。
堆是具有以下性质的完全二叉树，它的非叶子结点的关键字，都必须大于等于或小于等于其左右孩子的关键字。要求是完全二叉树的原因，是因为完全二叉树的层序遍历可以和序列索引一一对应。满足条件$R[i].key\ge R[2i].key$且$R[i].key\ge R[2i+1].key$的，称为大根堆。满足条件$R[i].key\le R[2i].key$且$R[i].key\le R[2i+1].key$的，称为小根堆。
我们可以很直接的发现这个结构的好处，大根堆可以直接找到最大值，小根堆可以直接找到最小值。我们以大根堆为例，如果我们能一直维护这个性质，每次只需要输出堆顶元素，即可得到一个有序序列。
我们先考虑给定一个序列，如何建立一个堆。这里有两种，自顶向下建堆法和自底向上建堆法。它们分别对应着上滤和下滤两种操作。
我们先来考虑下滤：
堆序性的一个好处是，当破坏一个结点的堆序性后，它的左孩子和右孩子以及孩子们的结构的堆序性不会被破坏。同时，当我们真正调整了不满足堆序性的结点后，破坏的性质也只会传递到一侧。这使得处理这个问题比旋转二叉树要简单许多。上图即表示了下滤的过程。
同时，由于完全二叉树的性质，后$[n/2]$的结点都是叶子结点，叶子结点天然满足堆序性。所以我们可以只下滤操作前$[n/2]$的结点。但不要误解，我们并不是不会交换后$[n/2]$的结点，因为叶子节点天然满足堆序性不代表其父结点满足。
1 | void HeapSift_down(rectype R[], int s, int t) |
类似地，我们也可以推出上滤操作：
然而上滤操作需要循环所有元素：
1 | void HeapSift_up(rectype R[], int s) |
注意C语言中，是向下取整的。
下面我们分析一下这两种筛选(sift)方法比较上的最坏时间复杂度，因为交换的时间复杂度分析起来过于复杂。注意，现在我们分析的过程是建堆的整个过程。
当采用自顶向下时，我们可以理解为是选取根结点，一个一个的插入堆的末尾。所以插入新的元素以后，需要上滤来进行调整；采用自底向上时，我们是对一个未调整过的序列，从它的倒数第二层结点（叶子结点的上一层）开始调整，所以是下滤。我们不难看出，上滤和下滤单次运行的时间复杂度都是$O(\mathrm{log}n)$。
一个直观的理解是：由于下滤是从顶向上，而越往上结点越少，所以相对上滤，可以理解为只有少数的结点会被比较相对较长的次数。现在我们定量计算一下，为了方便，我们考虑一颗满二叉树，对于这样的一个满二叉树，我们认为根结点深度为0，设整棵树层数为$h$，每一层的结点数量依次为$2^0,2^1,…,2^{h-1}$，由等比数列求和知$n=2^{h}-1$。
我们先考察下滤：当下滤时，高为0的结点最差情况下需要比较$h-1$次，它们有$2^{0}$个；高为1的结点最差需要比较$h-2$次，它们有$2^{1}$个，所以下滤建堆总代价为：
所以下滤建堆的时间复杂度是$O(n)$。
同理，上滤时：
所以上滤的时间复杂度为$O(n\mathrm{log}n)$。
在前面，我们实现上滤和下滤时，是直接写的一个迭代。实际上这个操作也是有递归版本的，我们以下滤为例：
所以在不特殊声明的时候，我们都用下滤。我们说清楚这个事情以后，其实堆排序就呼之欲出了：
1 | void HeapSort(rectype R[]) |
我们可以看到，运行时间主要消耗在初始建堆和对堆的反复筛选上。初始建堆虽然是$O(n)$，但后面每次要调整$n$次，每次是$O(\mathrm{log}n)$，所以堆排序的实际复杂度还是$O(n\mathrm{log}n)$。所以在有些资料里，其实并没有强调上滤和下滤，因为其只是一个常数级优化。堆排序的过程可以可视化为：
一个能让这个小节变得干净利落的原因是：堆排序对原始序列的状态并不敏感，并不会因为序列有序或者有大量重复数字，就显著降低效率。这是其与快速排序相比最大的优点。
然而大部分时候，在一些标准库的内置函数里，我们还是会使用基于快排的排序。这是因为堆排虽然很稳定，但由于它交换时的索引一般不会在一个局部内（i和2i），这会导致Cache命中率的降低，从而影响性能。
在实现堆排的过程中，我们其实随之实现了一种叫作优先队列(priority queue)的数据结构。显然，我们在排序中实现的这种结构满足这三个操作：
可以插入带优先级的元素，
取出最高优先级的元素，
可以以$O(1)$的时间复杂度查看最高优先级的元素（即堆顶），这个操作也叫peek。
Merge Sort
归并排序和前面介绍的排序都不一样，它是完全基于分治思想得出的。简单来说，你可以把含有$n$个记录的序列，看成$n$个有序的子表，每个子表长度为1，所以它们必然是有序的。之后两两归并，一直恢复到长度为$n$的序列为止。这种算法即二路归并排序。
归并两个有序表这个操作本身是很容易的，比如有两个表$A,B$。由于$A,B$都是有序的，就像两个牌堆一样，你每次只关注顶部哪张牌最小，就拿哪个即可。自然地，我们可以通过开辟一个辅助空间来实现这个归并操作：
1 | void Merge(rectype R[], int left, int right, int mid) |
我们发现，每次归并的时间复杂度是$O(n)$，因为我们都需要一次遍历完两个子序列，且两个子序列的长度和原序列长度只差一个常数倍。同理我们还需要申请一段同样长为$n$的内存空间，所以空间复杂度是$O(n)$。这是我们第一次遇到需要显式的使用额外空间的算法。但它并不会累计，因为每次Merge()结束后我们都会自动或手动的释放掉这段空间。
所以，我们按照之前说的二路归并的思路，可以写出如下代码：
1 | void MergeSort(rectype R[], int left, int right) |
整个过程可视化如下：
从动图里我们其实能清晰的看到三步：分(Divide)—治(Conquer)—合并(Combine)。我们可以分析整个递归的过程：
在每一层递归，最后的合并都一共需要$O(k\times \frac{n}{k})$的时间复杂度，同时一共递归$O(\mathrm{log}n)$层，所以归并排序的总的时间复杂度是$O(n\mathrm{log}n)$。之前我们讨论归并操作时说其需要$O(n)$的额外空间，在这里，除了这一部分额外空间以外，还有递归调用所隐式消耗的栈空间（类似快排）$O(\mathrm{log}n)$。但由于增长速度上$n>\mathrm{log}n$，所以我们一般都只说归并排序的空间复杂度是$O(n)$。
显然，我们可以仿照快速排序，用栈来模拟上面的归并排序：
1 | void MergeSort_no_recursive(rectype R[], int left, int right) { |
如果我们比较，递归时的快速排序和归并排序，会不难看出，快排中的partition()和归并排序中的merge()执行的顺序是不一样的。
1 | void QuickSort(rectype R[], int s, int t) |
其实，调用partition()和merge()的顺序，其实和二叉树的先序遍历及后序遍历是一样的。如果我们回顾二叉树那篇的blog，就不难发现为什么刚才非递归的归并排序需要两个栈了。当然，我们也可以通过在入栈时使用标记，通过这样的办法，我们可以统一掉快排和归并非递归的写法。
实际上，归并排序的非递归也有一种完全不需要栈的写法，它完全基于循环。这其实是因为，递归的写法和上面用栈模拟递归的写法中，得到“最小子序列”的操作，是没必要的。因为我们可以直接拿此时序列的索引，直接进行归并。比如直接按照索引的顺序，两两一对比较大小，然后进一步merge。
1 | void MergeSort_no_recursive2(rectype R[], int left, int right) { |
这种非递归的写法，外层循环每次以2为倍数扩大gap的值，比如第一次，gap是1，那么内部循环处理的分组其实就是0~0, 1~1,…，即每组一个。第二次排序，gap变为2，所以分组变成了0~1, 2~3, …，即每组两个。进而每组四个，一直到$n$个。
在最后，我们要讨论一下所谓的$K$路归并排序。我们将会认识到，归并这个操作并不是一个花哨的排序操作，而具有深远的意义。
实际上，$K$路归并排序并不是对于我们刚才所说的归并排序的复杂度意义上的优化。它是针对所谓外部排序时的一种策略。我们之前介绍的排序，其实都是在一个理想的条件下，对$n$个数进行排序。然而在计算机中，这个过程需要在内存中进行。而当$n$远远超出内存一次能容纳的大小时，我们只能将数据分成若干块，例如$m$块。然后从硬盘中读入一块，进行排序，然后再将这个部分有序的数据写入硬盘。
所以现在，对于$m$块局部有序的数据的排序，就成了一个问题。解决他们的办法即$K$路归并排序。
所谓$m$块有序数据，我们称为$m$个初始归并段。如果我们用二路归并，那么递归深度（这样便于一些定量上的分析）即$\mathrm{log}_2 m$，如果是$k$路即$\mathrm{log}_k m$。然而如果一味的增加$k$，每次归并时比较的次数就会增加。所以存在一个trade-off。
在这里我们着重讨论一下$k$路归并的这一个具体过程，假设共有$n$个元素。如果我们只是简单的线性扫描，找出每$k$路的最小值，然后比较。整个过程的时间复杂度即为$O(nk)$。一种优化的办法是用最小堆。初始建堆需要$O(k)$，每次调整堆需要$O(\mathrm{log}k)$，而总共需要比较$n$次，所以最后总的时间复杂度可以优化到$O(n\mathrm{log}k)$。还可以用胜者树，败者树来进一步优化，此处从略。
由于归并排序这种顺序归并的特点，使它天生就可以对链表进行排序。
Linear Time Sort
通过介绍那么多种排序，我们发现，最好也只能达到$O(n\mathrm{log}n)$。我们现在可以指出，$O(n\mathrm{log}n)$其实是基于比较的排序算法的下界。回想起前面所有的排序，无论是交换，还是选择，信息更新的方式都是：比较。
假设有3个数$a,b,c$。这三个数的大小关系有6种，即$n!$。如果把这个过程看成一个决策树，决策树一定有$n!$个叶子。考虑一个深度为$d$的二叉树，那么在它是满二叉树时，叶子最多，为$2^{d+1}-1$个。所以，如果一个二叉树有$n!$个叶子，那么其深度至少是$d\geqslant \lceil \log \left( n!+1 \right) \rceil -1$。所以，无论多么先进的基于比较的办法，都需要通过至少$\lceil \log \left( n!+1 \right) \rceil -1$的层数才能到达叶子节点。这个值通过斯特林公式：
可以进一步缩放：
所以，可以知道，基于比较的排序，下界确实是$O(n\mathrm{log}n)$。
一些基于运算的排序，不受这一下界的限制。例如桶排序(bucket sort)，它并不是特定的一种排序方法，它指的是将$n$个数据，通过大小，分配到$m$个“桶”里，分配的越均匀越好。假设每个桶里是$n/m$个元素，对每个桶应用归并排序，最后的时间复杂度即为$O(n\mathrm{log}\frac{n}{m})$。当$n/m$足够合适时，这个排序的时间复杂度就是接近线性$O(n)$的。当然，这也是空间换时间的一种表现。
这种排序在处理特定的数据时很有效，例如大量电话号码的排序。基数排序(radix sort)和计数排序(counting sort)均可以视作特殊的桶排。此处就略去关于这些近似线性时间的排序算法的详细介绍了。
Summary
我们可以把先前介绍的这些算法，他们的各种指标汇总到一张表中：
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 插入排序 | $O(n^2)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | 稳定 |
| 希尔排序 | $O(n^{1.3})$ | $O(n^{4/3})$ | $O(n^{7/6})$ | $O(1)$ | 不稳定 |
| 冒泡排序 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 稳定 |
| 快速排序 | $O(n\mathrm{log}n)$ | $O(n^2)$ | $O(n\mathrm{log}n)$ | $O(\mathrm{log}n)$ | 不稳定 |
| 选择排序 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 不稳定 |
| 堆排序 | $O(n\mathrm{log}n)$ | $O(n\mathrm{log}n)$ | $O(n\mathrm{log}n)$ | $O(1)$ | 不稳定 |
| 归并排序 | $O(n\mathrm{log}n)$ | $O(n\mathrm{log}n)$ | $O(n\mathrm{log}n)$ | $O(n)$ | 稳定 |
实际上，上述比较都忽略了常数因子。所以在排序少量数据时，有时使用简单的排序方式反而更好。关于算法的稳定性，我就直接记录结论了。分析哪些算法稳定与不稳定，可以当作复习各种算法的一个切入点。
最后我们讨论一下快速排序，归并排序，堆排序三者。这三者都有$O(n\mathrm{log}n)$的平均时间复杂度，快排的缺点是对于不同的输入，表现不够稳健。归并的缺点是需要$O(n)$的额外空间。堆排序的缺点是不能很好的支持局部性原理。所以具体使用哪些排序，是需要case by case的。例如在一些内存紧张的边缘设备中，我们就最好不要采用归并排序。
End
“悟已往之不谏，知来者之可追。”
