大家好，数据结构与算法这一讲的内容，我们继续第8章，内排序的学习。今天我们学习归并排序。
归并排序，它的思想呢就是一个典型的分治的思想。
也就是说我们先把大的待排序列划分为两个子序列。
然后呢，对每个子序列呢，继续采用归并的思想来分解。
得到了这两个子序列成为有序的序列以后呢，我们再把它们进行合并。
那我们对这样的一个待排序列， 首先呢我们是一直划分到每一个这样的子序列它是已经有序的为止。
那其实我们每一个单个元素它是有序的。
然后，我合并它们两两的这种相邻的有序子序列，然后得到得到更大的一个子序列。
然后逐层进行这样的归并。
那最后呢，我们就得到了一个排序的结果。
那我们看一下归并排序的算法框架。
那，对于这么一个待排的数组，我们需要开辟一个跟它一样大的这么一个临时的数组，来存我们中间的这些过渡的数据。
那我们给出了这个数组的待排的左下标和右下标这两端的位置。
然后呢，我们，对它呢，就进行一个均分的这么一个划分。
划分完以后呢，我们对于左半部分，递归地进行归并排序。右半部分，也是递归排序。
得到的这个左右子序列呢，已经是有序的子序列。
然后，我们来对这两个有序子序列进行一个归并的合并操作。
那我们来看这个合并操作呢，是，对这两个待排的有序子序列都是从左到右扫描 然后把它们归到新的数组。
开始的时候，我们先把这个待排的元素暂时都存入一个临时的数组。
然后呢，我们 设定两个下标。这个下标呢，是左数组的最左端和右数组的最左端。
那然后，我们这个结果数组呢，它也是从left这个下标开始。
那我们对这两个有序的数组，由这两个下标来界定。而且 这两个下标呢，要注意它们不能够越界。
也就是说，这个左边的子序列它不能够超过middle这样的一个下标。
右边呢，不能超过right这个下标。
那在这个界的范围之内呢， 我们来分别比较这两个子序列序列头那个元素，哪个更小。
更小的那一个呢，它就进到这个结果数组的当前的这个i 下标位。
然后这个i 呢，也是发生变化。
已经出了列的那一个子序列呢，它的下标位发生变化。
这里，我们特别要注意在这个判断这两个，子序列头，谁更小的时候呢，我们是偏爱左边的这个。
也就是说，当相等的时候，我们是取得左边那个元素。
啊，这样的话呢，它能够很好地保持这个数组它排序结果，它的稳定性。
出了这个循环以后呢，其实就是这样的一个情况。
有可能是只剩下了左序列。右序列呢已经处理完毕，也就是说，这个界已经是不满足了
或者是反过来。那这两种情况呢，只能出现一种。
其实也就是说，剩下左序列或者是剩下右序列, 那我们只需要把这个剩下的序列呢，逐个地拷贝到这个结果数组里面就可以了，
那整个归并的过程就完成了。
归并排序它跟快速排序类似呢，我们也可以考虑对它进行优化
特别是对于一些小的序列,那我们没有必要呢，对它还进行递归的操作。因为递归的代价是会很大的。
例如我们要准备这样的递归的堆占空间，然后呢，这些函数调用，它会花费一定的时间。
那，我们对这种基本有序的这些，小序列，采用一个简单的直接排序方法来处理。
还有一个优化呢，是Sedgewick提出来的。
我们回顾前面那个算法，要考虑子序列的下标不能够越界。
那也就是说，index 1 那个左子序列呢，要小于等于middle的那个值。
然后，index 2 那个下标呢，它要小于等于right那个界。
那，这种判断呢，它都是if判断,if判断它的代价是非常大的。
我们这个优化呢，它是从这个数组的两端来处理，向中间推进。
那当然这个，右边的那个子序列就被它进行了一个倒置，
那使得我们左右子序列，它们的这个序列尾呢，是在我们数组里面的相邻位置呢，它是背靠背的，那互为监视哨。
这样我们就可以简化这个边界的判断，加快我们的算法速度。
我们来看一下，Sedgewick 优化的思想。
那在划分的时候还是一样。在归并的时候，我们把这个右边子序列呢，是给它进行了一个倒置。
那这样的话呢，哦，左右这两个相邻的子序列，它们都是这个最大值呢，是紧挨在一起，就起到了一个背靠背的一个监视哨的作用。
那我们在归并这些元素的时候呢，我们的下标就可以从这两端往中间推进。
而不需要考虑说这个下标是不是越过了，这个子序列的数组。
因为我们如果一旦越过的话呢，比如说在这个左序列45已经处理完了以后，那它的这个原来的子序列下标，就变到了78这个位置。
那这样的话呢，它显然就已经是，我们再来比的时候这个剩下的64，它一定是小于这个78所在的这个位。
所以呢，它是自然不会越界的。
好那我们来看一下，它的一个演示。
我们首先这两个元素，那它在归并的时候呢，是非常方便的。
那如果是说对于长度为2的这两个数组来归并的时候你看，这里我们就给它倒置一下。
然后，你看到这两个下标，它如果是一个处理完了它另外一个会跟那个剩下的，更大的那个子序列呢，它会重叠，成为一个监视哨。
那我们再看这个更大一些的，那我们倒置以后，那我们挨个地进行处理。
那我们在45这个子序列，已经处理完了以后，那它的这个i1的这个下标就变到了这个地方，那就自然地去顶住了这个i2的这个数组里面的元素。
我们来看一下它的算法框架。
在这个优化里面，我们首先是对于这个短子序列我们是不进行递归的，也就是这一层的优化。
那如果是说这个序列的长度，它是小于这个阈值了，我们就直接地采用这样的一个插入排序来处理。
那在不同的系统里面呢，这个阈值测出来的是不一样的。你要根据你的应用环境，来进行一个测量。
不是所有的阈值都等于28。在我们这个例子里面它是等于28而已。
接着我们来看下面的这些代码呢，选这个中间的划分是一样的。
然后这两个递归，看起来也是一样。啊，差异主要就是对相邻的这个有序序列进行归并的时候,这个操作是不一样的，让我们来看一下它的操作。
对于这个归并的过程我们都是需要用到一个临时的数组的。
那我们在进行归并的时候，这两个子序列呢，我们左子序列还是跟原来的序一样,那右子序列呢，我们在存到临时数组里面呢， 是完全给它倒置一下。
这样的话呢，就达到了我们这个两个index它互为监视哨的这么一个作用。
然后我们循环呢，就只需要是从左到右，这样的，给它扫一下就可以。
然后我们保证 整个这个，子序列呢，都能够被处理到我们的目标的一个数组里面。
在比较的过程中，我们就可以直接的，只需要判断说，这个index1和index2，它们相应的这个元素数值的大小。
那小的呢，就直接入到这个结果数组里面，
而且呢，它相应的那个index域呢，也是往前加1
这样的话呢就，很大的简化了我们这样的一个归并的过程。
特别是这种边界的判断，以及我们原来其实还有一个扫尾的处理，也就是说某一个子序列处理完了，那么另外一个子序列呢，我们要全都给搬到结果数组里面。
但是在这里呢，因为它一旦的，某一个处理完了以后， 它那个index就跨到另外一个数组里面的最后那一位，不管你是从左边来还是从右边来
所以它就是达到一个监视哨的效果，就可以统一的进行处理。代码的长度也小很多了。
好，那我们看一下它的，时间和空间的一些代价。
首先呢，就是空间代价，它是比较大的，它需要用到一个跟我们待排数组一样大小的数组, 所以是Θ（n）。
那时间来说呢，我们就是分治法里面的分、治、合，这几个部分我们来看。
那划分呢，其实是很简单，就是除2，你就找到了那个它的划分点。
然后这个排序呢，它实际上呢，是一个递归的过程。
假设是，啊，用T(n)，来表示这样一个归并排序的时间的话呢，那它就是划分为两个这样的，规模为2分之n的这样的序列。
就是2乘以T，2分之n这样的代价。
归并的时间呢，对于这样的一个长度为n的待排的序列，它是由2分之n，这两个子序列来归并出来的。
这两个子序列呢，我都要看一遍。因此呢，我们是加上cn,这个c呢是一个常数了
对于小规模的情况，我们知道就可以设定它为常数。
那类似于我们前面快速排序 最佳情况的分解，那对这样的一个递推表达式，我们可以算出归并排序它的总时间代价，会是Θ(n)乘以log n 的。
这个其实完全不依赖于原始输入数组的情况。
它在最好，最差，平均情况下，都是Θ(n)乘以log n 的。
那最后留给大家几个思考题。
那首先呢就是普通的归并排序和Sedgewick的归并排序，它是不是稳定的？
这个要仔细思考一下，其中有一个是不稳定的。
那还有就是说，这两个归并排序的算法啊，哪一个会在时间效率上更高一些？
那我们可以从它们的总的这个元素的比较次数， 还有赋值的次数等等，这些方面来思考。
特别注意呢就是说，归并的时候，这个子序列下标，它是不是需要判断这个越界。
那我们知道，Sedgewick,它就是说想要让子序列这个下标呢，不需要判断越界。那这个能带来什么好处呢？大家也去想一想。
那谢谢大家。