归并排序遵循分治的思想：将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后合并这些子问题的解来建立原问题的解，归并排序的步骤如下：

　　划分：分解待排序的 n 个元素的序列成各具 n/2 个元素的两个子序列，将长数组的排序问题转换为短数组的排序问题，当待排序的序列长度为 1 时，递归划分结束

　　归并排序最吸引人的性质是它能保证将长度为 n 的数组排序所需的时间和 nlogn 成正比；它的主要缺点是所需的额外空间和 n 成正比。

　　空间复杂度：借助辅助数组实现合并，使用 O (n) 的额外空间；递归深度为 logn，使用 O (logn) 大小的栈帧空间。忽略低阶部分，所以空间复杂度为 O (n)

　　在上文实现中，我们在每次合并两个有序数组时，即使是很小的数组，我们都会创建一个新的 temp [] 数组，这部分耗时是归并排序运行时间的主要部分。更好的解决方案是将 temp [] 数组定义成 sort () 方法的局部变量，并将它作为参数传递给 merge () 方法，实现如下：

　　我们可以在执行合并前添加判断条件：如果nums[mid] = nums[mid + 1]时我们认为数组已经是有序的了，那么我们就跳过 merge () 方法。它不影响排序的递归调用，但是对任意有序的子数组算法的运行时间就变成线性的了，代码实现如下：

　　对小规模数组进行排序会使递归调用过于频繁，而使用插入排序处理小规模子数组一般可以将归并排序的运行时间缩短 10% ~ 15%，代码实现如下：

　　快速排序也遵循分治的思想，它与归并排序不同的是，快速排序是原地排序，而且快速排序会先排序当前数组，再对子数组进行排序，它的算法步骤如下：

　　哨兵划分：选取数组中最左端元素为基准数，将小于基准数的元素放在基准数左边，将大于基准数的元素放在基准数右边

　　快速排序有很多优点，但是在哨兵划分不平衡的情况下，算法的效率会比较低效。下面是对快速排序排序优化的一些方法：

　　对于小数组，快速排序比插入排序慢，快速排序的 sort () 方法在长度为 1 的子数组中也会调用一次，所以，在排序小数组时切换到插入排序排序的效率会更高，如下：

　　如果数组为倒序的情况下，选择最左端元素为基准数，那么每次哨兵划分会导致右数组长度为 0，进而使快速排序的时间复杂度为 O (n2)，为了尽可能避免这种情况，我们可以对基准数的选择进行优化，采用三取样切分的方法：选取数组最左端、中间和最右端这三个值的中位数为基准数，这样选择的基准数大概率不是区间的极值，时间复杂度为 O (n2) 的概率大大降低，代码实现如下：

　　在数组有大量重复元素的情况下，快速排序的递归性会使元素全部重复的子数组经常出现，而对这些数组进行快速排序是没有必要的，我们可以对它进行优化。

　　一个简单的想法是将数组切分为三部分，分别对应小于、等于和大于基准数的数组，每次将其中 “小于” 和 “大于” 的数组进行排序，那么最终也能得到排序的结果，这种策略下我们不会对等于基准数的子数组进行排序，提高了排序算法的效率，它的算法流程如下：

　　从左到右遍历数组，维护指针 l 使得 [left, l - 1] 中的元素都小于基准数，维护指针 r 使得 [r + 1, right] 中的元素都大于基准数，维护指针 mid 使得 [l, mid - 1] 中的元素都等于基准数，其中 [mid, r] 区间中的元素还未确定大小关系，图示如下：

　　这也是经典的荷兰国旗问题，因为这就好像用三种可能的主键值将数组排序一样，这三种主键值对应着荷兰国旗上的三种颜色巨人的肩膀