好了，我们继续来讲排序。
我们前两篇文章讲了三种排序，名字都不一样，但是时间复杂度都一样的——O(n^2)。这种比较高的时间复杂度，比较适合小规模的数据。
那么今天我们不能再讲小规模了，我们要讲讲适合大规模数据排序的算法，其时间复杂度为O(nlogn)。他们都是谁呢？——快速排序和归并排序
那么这两个排序的特点在哪里呢？——分而治之的思想
这个分而治之的思想很重要，我们可以用它解决非排序的问题
比如这篇blog的题目——如何在O(n)的时间复杂度内查找一个无序数组中的第K大元素？
好，我们一个一个来，先看看归并排序——
归并排序的思想——如果要排序一个数组，我们先把数组分为前后两个部分，（从中间来分），然后呢，对这个分好的前后两个部分分别排序。两个子数组排序成功后，再合并在一起就好。
In this way, 两个子数组合并成的整个数组就有序了。我们来看张示意图——
从上图中，我们可以看到，一共8个数字，分为了4 4个数字分别为一组。其中11 8 3 9再次分裂，成为11 8和3 9，然后再次分裂，成为11、 8、3、9四个集合。这时候每个集合中只有一个元素了，所以不能再分了。那分解完了，接下来就是合并。
合并时候要从小到大拍，1变2，2变4，然后4变8.
我认为写代码的一个难点就是在合并的时候进行从小到大的排序。
我们来畅想一个问题，如果原数组中的元素是奇数，假设是9个的话。第一次分，分为4和5。4个元素的不必多说，剩下呢个5个的，依然是奇数，继续分成2和3，然后3变成2和1，2最后再变成1和1.
其实看了上面的不断将大问题变成小问题的思想，跟之前我们学习的递归是非常相像的。
可以说，分而治之和递归二者的区别在于——分治是一种解决问题的处理思想，递归则是一种编程技巧。
好，那么我们下来的重点就是如何用递归来实现归并排序
递推公式：
merge_sort(p...r) = merge(merge_sort(p...q), merge_sort(q+1...r))
终止条件：
p >= r 不用再继续分解
我们来解释一下这个递推公式，merge_sort(p...r)表示给下标从p到r之间的数组进行排序。
等式右边则是转化为两个子问题, 其中q是p和r的中间值，也就是(p+r)/2。将两个子问题搞定后，再合并，整个就搞定了。
我们上面就说过一个问题，就是我认为的一个难点，它是什么来着——如何将分裂开来的子元素在合并的时候可以保证在合并完成后其合并后的数组也是有序的？
解决方法是什么呢？——
- 第一，我们先申请一个临时数组tmp，大小与A[p...r]相同。
- 第二，我们再用两个游标i和j，分别指向A[p...q]和A[q+1...r]的第一个元素。
- 第三，比较这两个元素A[i]和A[j]，如果A[i]<=A[j]，我们就把A[i]放入临时数组tmp中，同时i需要后移一位，否则，将A[j]中的元素放入数组tmp中，同时j后移一位。
- 第四，不断重复这个过程，直到其中一个子数组中的所有数据都放入tmp临时数组中，然后，再把另一个数组中的数据依次加入到临时数组的末尾，这个时候，临时数组tmp中存储的就是两个子数组合并之后的有序的数组啦~。
- 第五，也就是最后，将临时数组tmp中的数据copy到A[p...r]中。
有个问题，我们在编写merge函数时，如果使用之前提到的哨兵，会是什么样的？
再来解决之前问过的三个问题——
第一，归并排序是稳定的排序算法吗？
- 是的
第二，归并排序的时间复杂度是多少？
- 首先，merge()函数合并两个有序子数组的时间复杂度是O(n)，然后详细的先不说了。结果是O(nlogn)，重点是最好情况、最坏情况、平均情况都是O(nlogn)。
第三，MS的空度是多少？
- 我们首先要明确的一点是——快排的应用是比归并排序广泛的
为什么呢？——因为MS不是原地排序算法
到底是为啥，导致MS不是原地排序算法呢，这是因为MS的merge()函数，在合并两个有序子数组为一个有序数组时，需要借助额外的存储空间。
它的空度为O(n)，为什么空度不能像时度呢样累加呢？因为在任意时刻，CPU只会有一个函数在执行，也就只会有一个临时的内存空间在use。 - 所以说，由于临时内存空间最大也不会超过n个数据的大小，所以空度为O(n)。
好，我们下来再讲讲快排
快排的原理
我后面将快排写成QS。QS利用的也是分治思想。我们先来看看其核心思想——
如果要排序数组中下标从p到r的一组数据，我们选择p到r之间的任意一个数据作为pivot(分区点)
-
我们遍历p到r之间的数据，将小于pivot的放在左边，大于pivot的放在右边，of course, pivot放在中间。也就是说，数组p~r之间的数据被分成了3个部分。我们看下图——
快排核心思想原理图，将一组raw数据，分为3个区间
我们对于这三个区间，第一个和第三个，使用递归排序下标从p到q-1和q+1到r这两个数组中的数据，直到区间的长度缩小为1，此时，说明所有的数据有序。
上面讲的MS中，有一个merge()合并函数。
现在讲的QS中，有一个partition()分区函数。
partition()函数的核心就是——随机选择一个元素作为pivot(一般情况下，可以选择p到r区间的最后一个元素)，然后对A[p...r]分区，最后，函数返回pivot的下标。
上面的MS中，代码的实现有一个临时数组tmp, 在QS中，我们则不一样，我们申请两个临时数组X和Y，遍历A[p...r]，讲小于Pivot的copy到数组X，大于的给Y。最后，将数组X和Y中数据顺序拷贝到A[p...r]中。
